perm filename V2S.IN[1,DEK] blob
sn#285518 filedate 1977-05-29 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00014 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 folio 802 galley 1
C00020 00003 folio 805 galley 2
C00030 00004 folio 810 galley 3
C00053 00005 folio 818 galley 4
C00075 00006 folio 821 galley 5
C00096 00007 folio 824 galley 6
C00116 00008 folio 828 galley 7
C00137 00009 folio 832 galley 8
C00160 00010 folio 835 galley 9
C00182 00011 folio 842 galley 10
C00197 00012 folio 844 galley 11 "special italic figs in position 4"
C00213 00013 folio 845 galley 12
C00230 00014 folio 849 galley 13
C00242 ENDMK
C⊗;
folio 802 galley 1
0 {U0}{H9L11M29}|πW58320#Computer Programming!(Knuth/Addison-W
1 esley)!Answers!f.|4802!g.|41d|'{A6}!!|1|1This
3 extension of Euclid's algorithm includes most
9 of the features we have seen in previous extensions,
18 all at the same time, so it provides new insight
28 into the special cases already considered. To
35 prove that it is valid, note _rst that deg(|εv|β2)
44 |πdecreases in step C4, so the algorithm certainly
52 terminates. At the conclusion of the algorithm,
59 |εv|β1 |πis a common right divisor of |εV|β1
67 |πand |εV|β2, |πsince |εw|β1v|β1|4α=↓|4(|→α_↓1)|gnV|β1
71 |πand |ε|→α_↓w|β2v|β1|4α=↓|4(|→α_↓1)|gnV|β2;
73 |πalso if |εd |πis any common right divisor of
82 |εV|β1 |πand |εV|β2, |πit is a right divisor
90 of |εz|β1V|β1|4α+↓|4z|β2V|β2|4α=↓|4v|β1. |πHence
93 |εv|β1|4α=↓|4|πgerd(|εV|β1,|4V|β2). |πAlso if
96 |εm |πis any common left multiple of |εV|β1 |πand
105 |εV|β2, |πwe may assume without loss of generality
113 that |εm|4α=↓|4U|β1V|β1|4α=↓|4U|β2V|β2, |πsince
116 the sequence of values of |εQ |πdoes not depend
125 on |εU|β1 |πand |εU|β2. |πHence |εm|4α=↓|4(|→α_↓1)|gn(|→α_↓u
130 |β2z|ur|↔0|)1|))V|β1|4α=↓|4(|→α_↓1)|gn(u|β2z|ur|↔0|)2|))V|β2
130 |πis a multiple of |εz|ur|↔0|)1|)V|β1.|'!!|1|1|πIn
137 practice, if we just want to calculate gerd(|εV|β1,|4V|β2),
145 |πwe may suppress the computation of |εn, w|β1,
153 w|β2, w|ur|↔0|)1|), w|ur|↔0|)2|), z|β1, z|β2,
158 z|ur|↔0|)1|), z|ur|↔0|)2|); |πThese additional
162 quantities were added to the algorithm primarily
169 to make its validity more readily established.|'
176 !!|1|1|ε|*/Note:|\ |πNontrivial factorizations
179 of string polynomials, such as the example given
187 with this exercise, can be found from matrix
195 identities such as|'{A9}|↔a|(|εa|1!!|d51!!0|)|↔s|↔a|(b!!1|d5
198 1!!0|)|↔s|↔a|(|1c|1!!1|d51!!0|)|↔s|↔a|(0!!1|d51!|5|→α_↓|1c|1
198 |)|↔s|↔a|(0!!1|d51!|5|→α_↓b|)|↔s|↔a|(0!!1|d51!|5|→α_↓a|1|)|↔
198 s|4α=↓|4|↔a|(1!!0|d50!!1|)|↔s,|;{A9}|πwhich hold
201 even when multiplication is not commutative.
207 For example,|'{A9}|ε(abc|4α+↓|4a|4α+↓|4c)(1|4α+↓|4ba)|4α=↓|4
209 (ab|4α+↓|41)(cba|4α+↓|4a|4α+↓|4c).|;{A9}(|π(Compare
211 this with the ``continuant polynomials'' of Section
218 4.5.3.)|'{A3}|≡1|≡9|≡.|9|4(Solution by Michael
222 Fredman.) If such an algorithm exists, |εD |πis
230 a gerd by the argument in exercise 18. Let us
240 regard |εA |πand |εB |πas a single |ε2n|4α⊗↓|4n
248 |πmatrix |εC |πwhose _rst |εn |πrows are those
256 of |εA, |πand whose second |εn |πrows are those
265 of |εB. |πSimilarly, |εP |πand |εQ |πcan be combined
274 into a |ε2n|4α⊗↓|4n |πmatrix |εR; X |πand |εY
282 |πcan be combined into an |εn|4α⊗↓|42n |πmatrix
289 |εZ: |πthe desired conditions now reduce to two
297 equations |εC|4α=↓|4RD, D|4α=↓|4ZC. |πIf we can
303 _nd a |ε2n|4α⊗↓|42n |πinteger matrix |εU |πof
310 determinant |→|¬N1 such that the last |εn |πrows
318 of |εU|gα_↓|g1C |πare all zero, then |εR|4α=↓|4(|π_rst
325 |εn |πcolumns of |εU), D|4α=↓|4(|π_rst |εn |πrows
332 of |εU|gα_↓|g1C), Z|4α=↓|4(|π_rst |εn |πrows
337 of |εU|gα_↓|g1) |πsolves the desired conditions.
343 Hence, for example, the following triangularization
349 algorithm may be used (|εm|4α=↓|42n):|'{A3}!!|1|1|π|≡A|≡l|≡g
354 |≡o|≡r|≡i|≡t|≡h|≡m |≡T|≡.|9|4Let |εC |πbe an
359 |εm|4α⊗↓|4n |πmatrix of integers. This algorithm
365 _nds |εm|4α⊗↓|4m |πinteger matrices |εU |πand
371 |εV |πsuch that |εUV|4α=↓|4I |πand |εVC |πis
378 ``upper triangular.'' (The entry in row |εi |πand
386 column |εj |πof |εVC |πis zero if |εi|4|¬Q|4j.)|'
394 {A3}{I3.1H}|π!!|1|1|≡T|≡1|≡.|9Set |εU|4|¬L|4V|4|¬L|4I,
396 |πthe |εm|4α⊗↓|4m |πidentity matrix; and set
402 |εT|4|¬L|4C. (|πThroughout the algorithm we will
408 have |εT|4α=↓|4VC, UV|4α=↓|41.)|'{A3}!!|1|1|π|≡T|≡2|≡.|9Do
412 step T3 for |εj|4α=↓|41,|42,|4.|4.|4.|4,|4|πmin(|εm,|4n),
416 |πand terminate the algorithm.|'{A3}!!|1|1|≡T|≡3|≡.|9Perform
420 the following transformation zero or more times
428 until |εT|βi|βj |πis zero for all |εi|4|¬Q|4j:
435 |πLet |εT|βk|βj |πbe a nonzero element of |¬T|εT|βi|βj,|4T|β
442 (|βj|βα+↓|β1|β)|βj,|4.|4.|4.|4,|4T|βm|βj|¬Y |πhaving
444 the smallest absolute value. Interchange rows
450 |εk |πand |εj |πof |εT |πand of |εV; |πinterchange
459 columns |εk |πand |εj |πof |εU. |πThen subtract
467 |"l|εT|βi|βj/T|βj|βj|"L |πtimes row |εj |πfrom
472 row |εi, |πin matrices |εT |πand |εV, |πand add
481 the same multiple of column |εi |πto column |εj
490 |πin matrix |εU, |πfor |εj|4|¬W|4i|4|¬E|4m.|'
495 {A3}{IC}!!|1|1|πFor the stated example, the algorithm
501 yields (|f1!!2|d53!!4|))|4α=↓|4(|f1!!0|d53!!2|))(|f1!!2|d50!
502 |5|→α_↓1|)), (|f4!!3|d52!!1|))|4α=↓|4(|f4!!5|d52!!3|))(|f1!!
503 2|d50!|5|→α_↓1|)), (|f1!!2|d50|5!|→α_↓1|))|4α=↓|4(|f1!!0|d52
504 !|5|→α_↓2|))(|f1!!2|d53!!4|))|4α+↓|4(|f0!!0|d51!!0|))(|f4!!3
504 |d52!!1|)). (Actually any matrix with determinant
510 |→|¬N1 would be a gcrd in this case.)|'{A3}|≡2|≡0|≡.|9|4It
519 may be helpful to consider exercise 4.6.2<22
526 with |εp|gm |πreplaced by a small number |ε|≤e.|'
534 {A3}|≡2|≡1|≡.|9|4|πNote that Algorithm R is used
540 only when |εm|4α_↓|4n|4|¬E|41, |πand that the
546 coe∃cients are bounded by (25) with |εm|4α=↓|4n.
553 [|πThe stated formula is, in fact, the execution
561 time observed in practice, not merely an upper
569 bound. For more detailed information see G. E.
577 Collins, |εProc. |*/|↔O|↔m|↔o|↔l |\Summer Inst.
582 On Symbolic Math. Comp., |πRobert G. Tobey, ed.
590 (IBM Federal Systems Center, June 1969), 195<231.]|'
597 {A3}|≡2|≡2|≡.|9|4A sequence of signs cannot contain
603 two consecutive zeros, since |εu|βk|βα+↓|β1(x)
608 |πis a nonzero constant in (28). Moreover we
616 cannot have |→α+↓,|40,|4|→α+↓ or |→α_↓,|40,|4|→α_↓
621 as subsequences. The formula |εV(u,|4a)|4α_↓|4V(u,|4b)
626 |πis clearly valid when |εb|4α=↓|4a, |πso we
633 must only verify it as |εb |πincreases. The polynomials
642 |εu|βj(x) |πhave _nitely many roots, and |εV(u,|4b)
649 |πchanges only when |εb |πencounters or passes
656 such roots. Let |εx |πbe a root of some (possibly
666 several) |εu|βj. |πWhen |εb |πincreases from
672 |εx|4α_↓|4|≤e |πto |εx, |πthe sign sequence near
679 |εj |πgoes from |→α+↓,|4|→|¬N,|4|→α_↓ to |→α+↓,|40,|4|→α_↓
685 or from |→α_↓,|4|→|¬N,|4|→α+↓ to |→α_↓,|40,|4|→α+↓
690 if |εj|4|¬Q|40; |πand from |→α+↓,|4|→α_↓ to 0,|4|→α_↓
697 or from |→α_↓,|4|→α+↓ to 0,|4|→α+↓ if |εj|4α=↓|40.
704 (|πSince |εu|¬S(x) |πis the derivative, |εu|¬S(x)
710 |πis negative when |εu(x) |πis decreasing.) Thus
717 the net change in |εV |πis |→α_↓|ε|≤d|βj|β0.
724 |πWhen |εb |πincreases from |εx |πto |εx|4α+↓|4|≤e,
731 |πa similar argument shows that |εV |πremains
738 unchanged.|'!!|1|1[L. E. Heindel, |εJACM |π|≡1|≡8
744 (1971), 533<548, has applied these ideas to construct
752 algorithms for isolating the real zeroes of a
760 given polynomial |εu(x), |πin time bounded by
767 a polynomial in deg(|εu) |πand log|4|εN, |πwhere
774 all coe∃cients |εy|βj |πare integers with |¬G|εu|βj|¬G|4|¬E|
780 4N, |πand all operations are guaranteed to be
788 exact.]|'{A3}|≡2|≡3|≡.|9|4If |εv |πhas |εn|4α_↓|41
793 |πreal roots occurring between the |εn |πreal
800 roots of |εu, |πthen (by considering sign changes)
808 |εu(x)|πmod|4|εv(x) |πhas |εn|4α_↓|42 |πreal
812 roots lying between the |εn|4α_↓|41 |πof |εv.|'
819 {A24}{H10}|π|∨S|∨E|∨C|∨T|∨I|∨O|∨N |∨4|∨.|∨6|∨.|∨2|'
821 {A12}{H9}|9|1|≡1|≡.|9|4|πBy the principle of
825 inclusion and exclusion (Section 1.3.3), the
831 number of polynomials without linear factors
837 is |¬K|ε|βk|β|¬E|βn|4(|fp|d5k)p|gn|gα_↓|gk(|→α_↓1)|gk|4α=↓|4
838 p|gn|gα_↓|gp(p|4α_↓|41)|gp. |πThe stated probability
842 is therefore 1|4α_↓|4(1|4α_↓|41/|εp)|gp, |πwhich
846 is greater than |f1|d32|); in fact, it is greater
855 than |ε|f1|d32|) |πfor all |εn|4|¬R|41.|'{A3}|π|9|1|≡2|≡.|9|
860 4(a) We know that |εu(x) |πhas a representation
868 as a product of irreducible polynomials, and
875 the leading coe∃cients of these polynomials must
882 be units, since they divide the leading coe∃cient
890 of |εu(x). |πTherefore we may assume that |εu(x)
898 |πhas a representation as a product of monic
906 irreducible polynomials |εp|β1(x)|ge|r1|4.|4.|4.|4p|βr(x)|ge
908 |rr, |πwhere |εp|β1(x),|4.|4.|4.|4,|4p|βr(x)
911 |πare distinct. This representation is unique,
917 except for the order of the factors, so the conditions
927 on |εu(x), v(x), w(x) |πare satis_ed if and only
936 if|'{A9}|εv(x)|4α=↓|4p|β1(x)|g|"l|ge|r1|g/|g2|g|"L|4.|4.|4.|
937 4p|βr(x)|g|"l|ge|rr|g/|g2|"L, w(x)|4α=↓|4p|β1(x)|ge|r1|1|1|π
938 |gm|go|gd|1|1|g2|4.|4.|4.|4|εp|βr(x)|ge|rr|1|1|π|gm|go|gd|1|
938 1|g2.|;{A9}!!|1|1(b) The generating function
943 for the number of monic polynomials of degree
951 |εn |πis |ε1|4α+↓|4pz|4α+↓|4p|g2z|g2|4α+↓|4αo↓|4αo↓|4αo↓|4α=
953 ↓|41/(1|4α_↓|4pz). |πThe generating function
957 for the number of polynomials of degree |εn |πhaving
966 the form |εv(x)|g2, |πwhere |εv(x) |πis monic,
973 is 1|4α+↓|4|εpz|g2|4α+↓|4p|g2z|g4|4α+↓|4αo↓|4αo↓|4αo↓|4α=↓|4
974 1/(1|4α_↓|4pz|g2). |πIf the generating function
979 for the number of monic squarefree polynomials
986 of degree |εn |πis |εg(z), |πthen by part (a)
995 1/(1|4α_↓|4|εpz)|4α=↓|4g(z)/(1|4α_↓|4pz|g2).
996 |πHence |εg(z)|4α=↓|4(1|4α_↓|4pz|g2)/(1|4α_↓|4pz)|4α=↓|41|4α
997 +↓|4pz|4α+↓|4(p|g2|4α_↓|4p)z|g2|4α+↓|4(p|g3|4α_↓|4p|g2)z|g3|
997 4α+↓|4αo↓|4αo↓|4αo↓|4. |π|πThe answer is |εp|gn|4α_↓|4p|gn|g
1001 α_↓|g1 |πfor |εn|4|¬R|42. (|πCuriously, this
1006 proves that gcd{H11}({H9}|εu(x),|4u|¬S(x){H11}){H9}|4α=↓|4|π
1008 1 with probability 1|4α_↓|41/|εp; |πit is the
1015 sameas the probability that gcd({H11}({H9}|εu(x),|4v(x){H11}
1019 ){H9}|4α=↓|41 |πif |εu(x) |πand |εv(x) |πare
1025 |εindependent, |πby exercise 4.6.1<5.)|'{A3}|9|1|≡3|≡.|9|4Le
1029 t |εu(x)|4α=↓|4u|β1(x)|4.|4.|4.|4u|βr(x). |πThere
1032 is |εat most |πone such |εv(x), |πby the argument
1041 of Theorem 4.3.2C. |πThere is |εat least |πone
1049 if, for each |εj, |πwe can solve the system with
1059 |εw|βj(x)|4α=↓|41 |πand |εw|βk(x)|4α=↓|40 |πfor
1063 |εk|4|=|↔6α=↓|4j. |πA solution to the latter
1069 is |εv|β1(x)|4|≥7|βk|=|β|↔6|βα=↓|βj|4u|βk(x),
1071 |πwhere |εv|β1(x) |πand |εv|β2(x) |πcan be found
1078 satisfying|'{A9}|εv|β1(x)|4|≥7|βk|=|β|↔6|βα=↓|βj|4u|βk(x)|4α
1079 +↓|4v|β2(x)u|βj(x)|4α=↓|41,!!|πdeg(|εv|β1)|4|¬W|4|πdeg(|εu|β
1079 j),|;{A9}|πby the extension of Euclid's algorithm
1086 (exercise 4.6.1<3).|'{A1}|Ha{U31}TEAM|91|'{H9L11M29}W58320#|
folio 805 galley 2
1089 πComputer Programming|9(Knuth/Addison-Wesley)|9Answers|9f.|4
1090 805|9g.|42d|'{A6}|5|5|≡4|≡.|9|4|πThe unique factorization
1094 theorem gives the identity (|ε1|4α_↓|4pz)|gα_↓|g1|4α=↓|4|≥7|
1098 ur|)n|¬R1|)|4(1|4α_↓|4z|gn)|gα_↓|ga|rn|rp; |πafter
1100 taking logarithms, this can be rewritten |¬K|ur|)j|¬R1|)|4G|
1106 βp(z|gj)/j|4α=↓|4|¬K|ur|)k,j|¬R1|)|4a|βk|βpz|gk|gj/j|4α=↓|4|
1106 πln{H11}({H9}1/(1|4α_↓|4pz){H11}){H9}. |πThe
1108 stated identity now yields the answer |εG|βp(z)|4α=↓|4|¬K|ur
1114 |)m|¬R1|)|4|≤m(m)m|gα_↓|g1|4|πln{H11}({H9}1/(1|4α_↓|4pz|gm){
1114 H11}){H9}, |πfrom which we obtain |εa|βn|βp|4α=↓|4|¬K|ur|)d|
1119 ¬Dn|)|4|≤m(n/d)n|gα_↓|g1p|gd; |πlim|ur|)|εp|¬M|¬X|)|4a|βn|βp
1120 /p|gn|4α=↓|41/n. |πTo prove the stated idnetity,
1126 note that |¬K|ur|)|εn,j|¬R1|4|≤m(n)g(z|gn|gj)n|gα_↓|gtj|gα_↓
1128 |gt|4α=↓|4|¬K|ur|)m|¬R1|)|4g(z|gm)m|gα_↓|gt|4|¬K|ur|)n|¬Dm|)
1128 |4|≤m(n)|4α=↓|4g(z).|'{A3}|5|5|≡5|≡.|9|4|πLet
1130 |εa|βn|βp|βr |πbe the number of monic polynomials
1137 of degree |εn |πmodulo |εp |πhaving exactly |εr
1145 |πirreducible factors. Then |ε|λG|βp(z,|4w)|4α=↓|4|¬K|ur|)n,
1148 r|¬R0|)|4a|βn|βp|βrz|gnw|gr|4α=↓|4|πexp{H11}({H9}|ε|¬K|ε|βk|
1148 β|¬R|β1|4G|βp(z|gk)w|gk/k{H11}){H9}; |πcf. Eq.
1151 1.2.9<34. We have |¬K|ur|)|εn|¬R0|)|4A|βn|βpz|gn|4α=↓|4d|λG|
1154 βp(z/p,|4w)/dw|4|¬,|βw|βα=↓|β1|4α=↓|4{H11}({H9}|¬K|ur|)k|¬R1
1154 |)G|βp({H9}z|gk/p|gk){H11}){H9}|πexp{H11}({H9}ln(1/(1|4α_↓|4
1154 |εz)){H11}){H9}|4α=↓|4(|¬K|ur|)|εn|¬R1|)|4|πln{H11}({H9}1/(1
1154 |4α_↓|4|εp|g1|gα_↓|gnz|gn))|≤'(n)/n)/z{H11}){H9},
1155 |πhence |εA|βn|βp|4α=↓|4H|βn|4α+↓|41/2p|4α+↓|4O(p|gα_↓|g2)
1157 |πfor |εn|4|¬R|42. |πThe average value of |ε2|gr
1164 |πis the coe∃cient of |εz|gn |πin |ε|λG|βp(z/p,|42),
1171 |πnamely |εn|4α+↓|41|4α+↓|4(n|4α+↓|41)/p|4α+↓|4O(p|gα_↓|g2).
1172 (|πThe variance is of order |εn|g3, |πhowever:
1180 set |εw|4α=↓|44.)|'{A3}|5|5|≡6|≡.|9|4|πFor |ε0|4|¬E|4s|4|¬W|
1183 4p, x|4α_↓|4s |πis a factor of |εx|gp|4α_↓|4x
1190 (|πmodulo |εp) |πby Fermat's theorem. So |εx|gp|4α_↓|4x
1197 |πis a multiple of lcm{H11}({H9}|εx|4α_↓|40,
1202 x|4α_↓|41,|4.|4.|4.|4,|4x|4α_↓|4(p|4α_↓|41){J11}){H9}|4α=↓|4
1202 x|gp. (Note|*/: |\|πTherefore the Stirling numbers
1208 [|ε|fp|d5k|)] |πare multiples of |εp |πexcept
1214 when |εk|4α=↓|41, k|4α=↓|4p. |πEquation 1.2.6<41
1219 shows that the same statement is valid for Stirling
1228 numbers |¬A|ε|fp|d5k|)|¬S |πof the other kind.)|'
1234 {A3}|5|5|≡7|≡.|9|4The factors on the right are
1240 relatively prime, and each is a divisor of |εu(x),
1249 |πso their product divides |εu(x). |πOn the other
1257 hand,|'{A6}|εu(x)!!|πdivides!!|εv(x)|gp|4α_↓|4v(x)|4α=↓|4|≥u
1258 |uc|)0|¬Es|¬Wp|)|4{H11}({H9}v(x)|4α_↓|4s{H11}){H9},|;
1259 {A6}|πso it divides the right-hand side by exercise
1267 4.5.2<2.|'{A3}|5|5|≡8|≡.|9|4The vector which
1271 is output in step N3 is the only output whose
1281 |εk|πth component is nonzero.|'{A3}|5|5|≡9|≡.|9|4For
1286 example, start with |εx|5|¬L|51, y|5|¬L|51; |πthen
1292 repeatedly set |εR[x]|5|¬L|5y, x|5|¬L2x|4|πmod|4101,
1296 |εy|5|¬L|551y|4|πmod|4101, one hundred times.|'
1300 {A3}|≡1|≡0|≡.|9|4The matrix |εQ|4α_↓|4I |πbelow
1304 has a null space generated by the two vectors
1313 |εv|g[|g1|g]|4α=↓(1, 0, 0, 0, 0, 0, 0, 0), v|g[|g2|g]|4α=↓|4
1321 (0, 1, 1, 0, 0, 1, 1, 1). |πThe factorization
1331 is|'{A6}(|εx|g6|4α+↓|4x|g5|4α+↓|4x|g4|4α+↓|4x|4α+↓|41)(x|g2|
1332 4α+↓|4x|4α+↓|41).|;{A6}{H7L9}|∂!!!!|9|5|∂!!!!!!!!!!!!!!!!!!|
1333 5|∂!!!!!!|∂!!!!!!!!!!!!!!!|9|6|∂!!!!|9|5|∂|E|;
1334 |>|;|εp|4α=↓|42|;|;p|4α=↓|45|;>{A6}!!!!|9|40!!0!!0!!0!!0!!0!
1340 !0!!0!!!!!!0!!0!!0!!0!!0!!0!!0|'!!!!|9|40!!1!!1!!0!!0!!0!!0!
1341 !0!!!!!!0!!4!!0!!0!!0!!1!!0|'!!!!|9|40!!0!!1!!0!!1!!0!!0!!0!
1342 !!!!!0!!2!!2!!0!!4!!3!!4|'!!!!|9|40!!0!!0!!1!!0!!0!!1!!0!!!!
1343 !!0!!1!!4!!4!!4!!2!!1|'!!!!|9|41!!0!!0!!1!!0!!0!!1!!0!!!!!!2
1344 !!2!!2!!3!!4!!3!!2|'!!!!|9|41!!0!!1!!1!!1!!0!!0!!0!!!!!!0!!0
1345 !!4!!0!!1!!3!!2|'!!!!|9|40!!0!!1!!0!!1!!1!!0!!1!!!!!!3!!0!!2
1346 !!1!!4!!2!!1|'!!!!|9|41!!1!!0!!1!!1!!1!!0!!1|'
1348 {A12}{H9L11}|≡1|≡1|≡.|9|4|πRemoving the trivial
1351 factor |εx, |πthe matrix |εQ|4α_↓|4I |πabove
1357 has a null space generated by (1, 0, 0, 0, 0,
1368 0, 0) and (0, 3, 1, 4, 1, 2, 1). The factorization
1380 is|'{A6}|εx(x|g2|4α+↓|43x|4α+↓|44)(x|g5|4α+↓|42x|g4|4α+↓|4x|
1381 g3|4α+↓|4rx|g2|4α+↓|4x|4α+↓|43).|;{A6}|≡1|≡2|≡.|9|πIf
1383 |εp|4α=↓|42, (x|4α+↓|41)|g4|4α=↓|4x|g4|4α+↓|41.
1385 |πIf |εp|4α=↓|48k|4α+↓|41, Q|4α_↓|4I |πis the
1390 zero matrix, so there are four factors. For other
1399 values of |εp |πwe have|'{A6}{H9L11}!!!!!!!!|9|7|εp|4α=↓|48k
1404 |4α+↓|43!!!!|5|5p|4α=↓|48k|4α+↓|45!!!!|5|5p|4α=↓|48k|4α+↓|47
1404 |'{A6}{M32}|h|εQ|4α_↓|4I|4α=↓|4|8|8|n0!!|8|80!!|8|80!!|8|80!
1405 |9|50!!|8|80!!0!!|8|80!|9|50!!|8|80!!|8|80!!|8|80|'
1406 {A6}|εQ|4α_↓|4I|4α=↓|4{B6}|8|80!!|→α_↓1!!|8|80!!|8|81!|9|50!
1406 !|→α_↓2!!0!!|8|80!|9|50!!|→α_↓1!!|8|80!!|→α_↓1|'
1407 |hQ|4α_↓|4I|4α=↓|4|8|8|n0!!|8|80!!|→α_↓2!!|8|80!|9|50!!|8|80
1407 !!0!!|8|80!|9|50!!|8|80!!|→α_↓2!!|8|80|'Q|4α_↓|4I|4α=↓|4|8|8
1408 0!!|8|81!!|8|80!!|→α_↓1!|9|50!!|8|80!!0!!|8|8|→α_↓2!|9|50!!|
1408 →α_↓1!!|8|80!!|→α_↓1|'{A6}{M29}|πHere |εQ|4α_↓|4I
1411 |πhas rank 2, so there are 4|4α_↓|42|4α=↓|42
1418 factors. (But it is easy to prove that |εx|g4|4α+↓|41
1427 |πis irreducible over the integers, since it
1434 has no linear factors and the coe∃cient of |εx
1443 |πin any factor of degree two must be less than
1453 or equal to 2|4in absolute value by exercise
1461 20. For all |εk|4|¬R|42, |πH. P. F. Swinnerton-Dyer
1469 has exhibited polynomials of degree |ε2|gk |πwhich
1476 are irreducible over the integers, but which
1483 split completely into linear and quadratic factors
1490 modulo every prime. For degree 8, his example
1498 is |εx|g8|4α_↓|416x|g6|4α+↓|488x|g4|4α+↓192x|g2|4α+↓|4144,
1500 |πhaving roots |ε{U0}{H9L11M29}|πW58320#Computer
folio 810 galley 3
1503 Programming!(Knuth/Addison-Wesley)!Answers!f.|4810!g.|43d|'
1504 {A6}|π|≡1|≡6|≡.|9|4(a) Substitute polynomials
1507 modulo |εp |πfor integers, in the proof for |εn|4α=↓|41.
1516 |π(b) The proof in exercise 3.2.1.2<16 carries
1523 over to any _nite _eld. (c) Since |εx|4α=↓|4|≤j|gk
1531 |πfor some |εk, x|gp|in|4α=↓|4x |πin the _eld.
1538 Furthermore, the elements |εy |πwhich satisfy
1544 the equation |εy|gp|im|4α=↓|4y |πin the _eld
1550 are closed under addition, and closed under multiplication;
1558 so if |εx|gp|im|4α=↓|4x, |πthen |ε|≤j |π(being
1564 a polynomial in |εx |πwith integer coe∃cients)
1571 satis_es |ε|≤j|gp|im|4α=↓|4|≤j.|'{A3}|π|≡1|≡7|≡.|9|4If
1574 |ε|≤j |πis a primitive root, each nonzero element
1582 is some power of |ε|≤j. |πHence the order must
1591 be a divisor of 13|g2|4α_↓|41|4α=↓|42|g3|4αo↓|43|4αo↓|47,
1596 and |ε|≤'(f) |πelements have order |εf.|'{A6}|∂!!|9|∂!!!|9|∂
1602 !!!|∂!!!|9|∂!!!|∂!!!|∂!!!|9|∂!!!|9|∂|E|;|>f|;
1605 |≤'(f)|;f|;|≤'(f)|;f|;|≤'(f)|;f|;|≤'(f)|;>{A2}|>
1614 1|;1|;|9|13|;2|;|9|17|;|9|16|;|9|121|;12|;>|>
1624 2|;1|;|9|16|;2|;14|;|9|16|;|9|142|;12|;>|>4|;
1635 2|;12|;4|;28|;12|;|9|184|;24|;>|>8|;4|;24|;8|;
1648 56|;24|;168|;48|;>{A6}|π|≡1|≡9|≡.|9|4If |εu(x)|4α=↓|4v(x)w(x
1654 ) |πwith deg(|εv)|πdeg(|εw)|4|¬R|41, |πthen |εu|βnX|gn|4|"o|
1658 4v(x)w(x) (|πmodulo |εp). |πBy unique factorization
1664 modulo |εp, |πall but the{A3}|π|≡2|≡0|≡.|9|4(a)
1669 |ε|¬K|4(|≤au|βj|4α_↓|4u|βj|βα_↓|β1)(|=3|≤a|=3u|βj|4α_↓|4|=3u
1669 |βj|βα_↓|β1)|4α=↓|4|¬K|4(u|βj|4α_↓|4|=3|≤au|βj|βα_↓|β1)(|=3u
1669 |βj|4α_↓|4|≤a|=3u↓|β1). (|πb) We may assume that
1675 |εu|β0|4|=|↔6α=↓|40. |πLet |εm(u)|4α=↓|4|≥7|β1|β|¬E|βj|β|¬E|
1677 βn|4|πmin(|ε1,|4|¬G|≤a|βj|¬G)|4α=↓|4u|β0/M(u)u|βn.
1678 |πWhenever |¬G|ε|≤a|βj|¬G|4|¬W|41, |πchange the
1682 factor |εx|4α_↓|4|≤a|βj |πto |ε|=3|≤a|βjx|4α_↓|41
1686 |πin |εu(x); |πthis doesn't a=ect |ε|¬Gu|¬G.
1692 |πNow looking at the leading and trailing coe∃cients
1700 only, we have |ε|¬Gu|¬G|g2|4|¬R|4|¬Gu|βn|¬G|g2m(u)|g2|4α+↓|4
1703 |¬Gu|βn|¬G|g2M(u)|g2; |πhence we obtain the slightly
1709 stronger result |εM(u)|g2|4|¬E|4{H11}({H9}|¬Gu|¬G|g2|4α+↓|4(
1711 |¬Gu|¬G|g4|4α_↓|44|¬Gu|β0u|βn|¬G|g2)|g|f1|d32|){H11}){H9}/2|
1711 ¬Gu|βn|¬G|g2. |π(c) |εu|βj|4α=↓|4u|βm|4|¬K|4|≤a|βi|m1|4.|4.|
1713 4.|4|≤a|βi|mm|mα_↓|mj, |πan elementary symmetric
1717 function, hence |ε|¬Hu|βj|¬G|4|¬E|4|¬Gu|βm|¬G|4|¬K|4|≤b|βi|m
1719 1|4.|4.|4.|4|≤b|βi|mm|mα_↓|mj |πwhere |ε|≤b|βi|4α=↓|4|πmax(1
1721 ,|4|ε|¬G|≤a|βi|¬G). |πWe complete the proof by
1727 showing that when 1|4|¬E|4|εx|β1,|4.|4.|4.|4,|4x|βn
1731 |πand |εx|β1|4.|4.|4.|4x|βn|4α=↓|4M, |πthe elementary
1735 symmetric function |ε|≤s|βn|βk|4α=↓|4|¬K|4x|βi|m1|4.|4.|4.|4
1737 x|βi|mk |πis |→|¬E(|ε|fnα_↓1|d5kα_↓1|))M|4α+↓|4(|fnα_↓1|d5k|
1739 )), |πthe value assumed when |εx|β1|4α=↓|4αo↓|4αo↓|4αo↓|4α=↓
1744 |4x|βn|βα_↓|β1|4α=↓|41 |πand |εx|βn|4α=↓|4M.
1747 (|πFor if |εx|β1|4|¬E|4αo↓|4αo↓|4αo↓|4|¬E|4x|βn|4|¬W|4M,
1750 |πthe transformation |εx|βn|4|¬L|4x|βn|βα_↓|β1x|βn,
1753 x|βn|βα_↓|β1|4|¬L|41 |πincreases |ε|≤s|βn|βk
1756 |πby |ε|≤s|β(|βn|βα_↓|β2|β)|β(|βk|βα_↓|β1|β)(x|βn|4α_↓|41)(x
1757 |βn|βα_↓|β1|4α_↓|41)|4|¬Q|40.) |π(d) |ε|¬Gv|βj|¬G|4|¬E|4|¬Gv
1759 |βm|¬G{H11}({H9}(|fmα_↓1|d5j|))M(v)|4α+↓|4(|fmα_↓1|d5jα_↓1|)
1759 ){H11}){H9}|4|¬E|4|¬GU|βn|¬G{H11}({H9}(|fmα_↓1|d5j|))M(u)|4α
1759 +↓|4(|fmα_↓1|d5jα_↓1|)){H11}){H9} |πsince |ε|¬Gv|βm|¬G|4|¬E|
1761 4|¬Gu|βn|¬G |πand |εM(v)|4|¬E|4M(u). [|πThese
1765 results are slight extensions of inequalities
1771 due to M. Mignotte, |εMath. Comp. |π|≡2|≡8 (1974),
1779 1153<1157.]|'{A3}|≡2|≡1|≡.|9|4(a) |¬j|ur1|)0|)|4(|εu|βne(n|≤
1781 u)|4α+↓|4αo↓|4αo↓|4αo↓|4α+↓|4u|β0)(|=3u|βne(|→α_↓n|≤u)|4α+↓|
1781 4αo↓|4αo↓|4αo↓|4α+↓|4|=3u|β0)|4d|≤u|4α=↓|4|¬Gu|βn|¬G|g2|4α+↓
1781 |4αo↓|4αo↓|4αo↓|4α+↓|4|¬Gu|β0|¬G|g2 |πsince |ε|¬J|ur1|)0|)|4
1783 e(j|≤u)e(|→α_↓k|≤u)|4d|≤u|4α=↓|4|≤d|βj|βk; |πnow
1785 use induction on |εt. |π(b) Since |ε|¬Gv|βj|¬G|4|¬E|4(|fm|d5
1791 j|))M(v)|¬Gv|βm|¬G |πwe conclude that |ε|¬Gv|¬G|g2|4|¬E|4(|f
1795 2m|d5m|))M(v)|g2|¬Gv|βm|¬G|g2. |πHence |ε|¬Gv|¬G|g2|¬Gw|¬G|g
1797 2|4|¬E|4(|f2m|d5m|))(|f2k|d5k|))M(v)|g2M(w)|g2|¬Gv|βmw|βk|¬G
1797 |g2|4α=↓|4f(m,|4k)M(u)|g2|¬Gu|βn|¬G|g2|4|¬E|4f(m,|4k)|¬Gu|¬G
1797 |g2. [|πSlightly better values for |εf(m,|4k)
1803 |πare possible based on the more detailed information
1811 in exercise 20.] (c) The case |εt|4α=↓|43 |πsu∃ces
1819 to show how to get from |εt|4α_↓|41 |πto |εt.
1828 |πWhen |εt|4α=↓|42 |πwe have shown that, for
1835 all |ε|≤u|β1, |¬J|ur1|)0|)|4|¬J|ur1|)0|)|4|¬J|ur1|)0|)|4|¬J|
1837 ur1|)0|)|4|¬Gv{H11}({H9}e(|≤u|β1), e(|≤f|β2),
1839 e(|≤f|β3){H11}){H9}|¬G|g2|4|¬Gw{H11}({H9}e(|≤u|β1),
1840 e(|≤c|β2), e(|≤c|β3){H11}){H9}|¬G|g2|4d|≤f|β2|4d|≤f|β3|4d|≤c
1841 |β2|4d|≤c|β3|4|¬E|4f(m|β2,|4k|β2)f(m|β3,|4k|β3)|4|¬J|ur1|)0|
1841 )|4|¬J|ur1|)0|)|4|¬GV{H11}({H9}e(|≤u|β1), e(|≤u|β2),
1843 e(|≤u|β3){H11}){H9}|¬G|g2|4|¬Gw{H11}({H9}e(|≤u|β1),
1844 e(|≤u|β2), e(|≤u|β3){H11}){H9}|¬G|g2|4d|≤u|β2|4d|≤u|β3.
1846 |πFor all |ε|≤f|β2, |≤f|β3, |≤c|β2, |≤c|β3 |πwe
1853 have also shown that |ε|¬J|ur1|)0|)|4|¬J|ur1|)0|)|4|¬GV{H11}
1857 ({H9}e(|≤f|β1), e(|≤f|β2), e(|≤f|β3){H11}){H9}|¬G|g2|4|¬Gw{H
1859 11}({H9}e(|≤c|β1), e(|≤c|β2), e(|≤c|β3){H11}){H9}|¬G|g2|4d|≤
1861 f|β1|4d|≤c|β1|4|¬E|4f(m|β1,|4k|β1)|4|¬J|ur1|)0|)|4|¬Gv{H11}(
1861 {H9}e(|≤u|β1), e(|≤f|β2), e(|≤f|β3){H11}){H9}|¬G|g2|4|¬Gw{H1
1863 1}({H9}e(|≤u|β1), e(|≤c|β2), e(|≤c|β3){H11}){H9}|¬G|g2|4d|≤u
1865 |β1. |πIntegrate the former inequality wi7h respect
1872 to |ε|≤u|β1 |πand the latter with respect to
1880 |ε|≤f|β2, |≤f|β3, |≤c|β2, |≤c|β3. [|πThis method
1886 was used by A. O. Gel'fond in |εTranscendental
1894 and Algebraic Numbers (|πNew York: Dover, 1960),
1901 Section 3.4, to derive a slightly di=erent result.]|'
1909 {A3}|≡2|≡2|≡.|9|4More generally, assume that
1913 |εu(x)|4|"o|4v(x)w(x) (|πmodulo |εq), a(x)v(x)|4α+↓|4b(x)w(x
1916 )|4|"o|41 (|πmodulo |εp), |πand |εc|λ3(v)|4|"o|41
1921 (|πmodulo |εr), |πdeg(|εa)|4|¬W|4|πdeg(|εw),
1924 |πdeg(|εh)|4|¬W|4|πdeg(|εv), |πdeg(|εu)|4α=↓|4|πdeg(|εv)|4α+
1925 ↓|4|πdeg(|εw), |πwhere |εr|4α=↓|4|πgcd(|εp,|4q)
1928 |πand |εp,|4q |πneedn't be prime. We shall construct
1936 polynomials |εV(x)|4|"o|4v(x) |πand |εW(x)|4|"o|4w(x)
1940 (|πmodulo |εq) |πsuch that |εu(x)|4|"o|4V(x)W(x)
1945 (|πmodulo |εqr), |λ3(V)|4α=↓|4|λ3(v), |πdeg(|εV)|4α=↓|4|πdeg
1948 (|εW)|4α=↓|4|πdeg(|εw); |πfurthermore, if |εr
1952 |πis prime, the results will be unique modulo
1960 |εqr.|'!!|1|1|πThe problem asks us to _nd |ε|=3v(x)
1968 |πand |ε|=3w(x) |πwith |εV(x)|4α=↓|4v(x)|4α+↓|4q|=3v(x),
1972 {H11}({H9}N(x)|4α=↓|4w(x)|4α+↓|4q|=3w(x), |πdeg(|ε|=3v)|4|¬W
1973 |4|πdeg(|εv), |πdeg(|ε|=3w)|4|¬E|4|πdeg(|εw);
1975 |πand the other condition {H11}({H9}|εv(x)|4α+↓|4q|=3v(x){H1
1979 1})({H9}w(x)|4α+↓|4q|=3w(x){H11}){H9}|4|"o|4u(x)
1980 (|πmodulo |εqr) |πis equivalent to |ε|=3w(x)v(x)|4α+↓|4|=3v(
1985 x)w(x)|4|"o|4f(x) (|πmodulo |εr), |πwhere |εu(x)|4|"o|4v(x)w
1989 (x)|4α+↓|4qf(x) (|πmodulo |εqr). |πWe have |ε{H11}({H9}a(x)f
1994 (x)|4α+↓|4t(x)w(x){H11}){H9}v(x)|4α+↓|4{H11}({H9}b(x)f(x)|4α
1994 _↓|4t(x)v(x){H11}){H9}w(x)|4|"o|4f(x) (|πmodulo
1996 |εr) |πfor all |εt(x). |πSince |λ3(|εv) |πhas
2003 an inverse modulo |εr, |πwe can _nd a quotient
2012 |εt(x) |πby Algorithm 4.6.1D such that deg(|εbf|4α_↓|4tv)|4|
2018 ¬W|4|πdeg(|εv); |πfor this |εt(x), |πdeg(|εaf|4α+↓|4tw)|4|¬E
2022 |4|πdeg(|εw), |πsince deg(|εf)|4|¬E|4|πdeg(|εu)|4α=↓|4|πdeg(
2024 |εv)|4α+↓|4|πdeg(|εw). |πThus the desired solution
2029 is |ε|=3v(x)|4α=↓|4b(x)f(x)|4α_↓|4t(x)v(x)|4α=↓|4b(x)f(x)|πm
2030 od|4|εv(x), |=3w(x)|4α=↓|4a(x)f(x)|4α+↓|4t(x)w(x).
2032 |πIf {H11}({H9}|ε|=∩|=3v(x),|4|=∩|=3w(x){H11})
2034 |πis another solution, we have {H11}({H9}|ε|=3w(x)|4α_↓|4|=∩
2039 |=3w(x){H11}){H9}v(x)|4|"o|4{H11}({H9}|=∩|=3v(x)|4α_↓|4|=3v(
2039 x){H11}){H9}w(x) (|πmodulo |εr). |πThus if |εr
2045 |πis prime, |εv(x) |πmust divide |ε|=∩|=3v(x)|4α_↓|4|=3v(x);
2050 |πbut deg(|ε|=∩|=3v|4α_↓|4|=3v)|4|¬W|4|πdeg(|εv),
2053 |πso |ε|=∩|=3v(x)|4α=↓|4|=3v(x) |πand |ε|=∩|=3w(x)|4α=↓|4|=3
2056 w(x).|'!!|1|1|πFor |εp|4α=↓|42, |πthe factorization
2061 proceeds as follows (writing only the coe∃cients,
2068 and using bars for negative digits): Exercise
2075 10 says that |εv|β1(x)|4α=↓|4(|=∩1|4|=∩1|4|=∩1),
2079 |εw|β1(x)|4α=↓|4(|=∩1|4|=∩1|4|=∩1|40|40|4|=∩1|4|=∩1)
2080 |πin one-bit two's complement notation. Euclid's
2086 extended algorithm yields |εa(x)|4α=↓|4(1|40|40|40|40|41),
2090 b(x)|4α=↓|4(1|40). |πThe factor |εv(x)|4α=↓|4x|g2|4α+↓|4c|β1
2093 x|4α+↓|4c|β0 |πmust have |ε|¬Gc|β1|¬G|4|¬E|4|"l1|4α+↓|4|¬H|v
2096 4113|)|"L|4α=↓|411, |¬Gc|β0|¬G|4|¬E|410, |πby
2099 exercise 20. Three applications of Hensel's lemma
2106 yield |εv|β4(x)|4α=↓|4(1|43|4|=∩1), w|β4(x)|4α=↓|4(1|4|=∩3|4
2108 |=∩5|4|=∩4|44|4|=∩3|45). |πThus |εc|β1|4|"o|43
2111 |πand |εc|β0|4|"o|4|→α_↓1 (|πmodulo 16); the
2116 only possible quadratic factor of |εu(x) |πis
2123 |εx|g2|4α+↓|43x|4α_↓|41. |πDivision fails, so
2127 |εu(x) |πis irreducible. (Since we have now proved
2135 the irreducibility of this beloved polynomial
2141 by four separate methods, it is unlikely that
2149 it has any factors.)|'!!|1|1Hans Zassenhaus has
2156 observed that we can often speed up such calculations
2165 by increasing |εp |πas well as |εq: |πIn the
2174 above notation, we can _nd |εA(x), B(x) |πsuch
2182 that |εA(x)V(x)|4α+↓|4B(x)W(x)|4|"o|41 (|πmodulo
2185 |εpr), |πnamely by taking |εA(x)|4α=↓|4a(x)|4α+↓|4p|=3a(x),
2190 B(x)|4α=↓|4b(x)|4α+↓|4p|=∩b(x), |πwhere |ε|=3a(x)V(x)|4α+↓|4
2192 |=∩b(x)W(x)|4|"o|4g(x) (|πmodulo |εr), a(x)V(x)|4α+↓|4b(x)W(
2195 x)|4|"o|41|4α_↓|4pg(x) (|πmodulo |εpr). |πWe
2199 can also _nd |εC |πwith |λ3|ε(V)C|4|"o|41 (|πmodulo
2206 |εpr). |πIn this way we can lift a squarefree
2215 factorization |εu(x)|4|"o|4v(x)w(x) (|πmodulo
2218 |εp) |πto its unique extensions modulo |εp|g2,
2225 p|g4, p|g8, p|g1|g6, |πetc. However, this ``accelerated''
2232 procedure reaches a point of diminishing returns
2239 in practice, as soon as we get to double-precision
2248 moduli, since the time for multiplying multiprecision
2255 numbers in practical ranges outweighs the advantage
2262 of squaring the modulus directly. From a computational
2270 standpoint it seems best to work with the successive
2279 moduli |εp| p|g2, p|g4, p|g8,|4.|4.|4.|4, p|gE,
2284 p|gE|gα+↓|ge, p|gE|gα+↓|g2|ge, p|gE|gα+↓|g3|ge,|4.|4.|4.|4,
2287 |πwhere |εE |πis the smallest power of 2 with
2296 |εp|gE |πgreater than single precision and |εe
2303 |πis the largest integer such that |εp|ge |πhas
2311 single precision.|'!!|1|1Hensel's Lemma, which
2316 he introduced in order to demonstrate the factorization
2324 of polynomials over the _eld of |εp-|πaddic numbers
2332 (see exercise 4.1<31), can be generalized in
2339 several ways. First, if there are more factors,
2347 say |εu(x)|4|"o|4v|β1(x)v|β2(x)v|β3(x) (|πmodulo
2350 |εp), |πwe can _nd |εa|β1(x), a|β2(x), a|β3(x)
2357 |πsuch that |εa|β1(x)v|β2(x)v|β3(x)|4α+↓|4a|β2(x)v|β1(x)v|β3
2359 (x)|4α+↓|4a|β3(x)v|β1(x)v|β2(x)|4|"o|41 (|πmodulo
2361 |εp), |πdeg(|εa|βi)|4|¬W|4|πdeg(|εv|βi). (|πIn
2364 essence, |ε1/u(x) |πis expanded in partial fractions
2371 as |ε|¬K|4a|βi(x)/v|βi(x).) |πAn exactly analogous
2376 construction now allows us to lift the factorization
2384 without changing the leading coe∃cients of |εv|β1
2391 |πand |εv|β2; |πwe take |ε|=3v|β1(x)|4α=↓|4a|β1(x)f(x)|πmod|
2395 4|εv|β1(x), |=3v|β2(x)|4α=↓|4a|β2(x)f(x)|πmod|4|εv|β2(x),
2397 |πetc. Another important generalization is to
2403 several simultaneous moduli, of the respective
2409 forms |εp|ge, (x|β2|4α_↓|4a|β2)|gn|r2,|4.|4.|4.|4,
2412 (x|βt|4α_↓|4a|βt)|gn|rt, |πwhen performing multivariate
2416 gcds and factorizations. Cf. D. Y. Y. Yun, Ph.D.
2425 Thesis (M.I.T., 1974).|'{A3}|≡2|≡3|≡.|9|4The
2429 discriminant of |εu(x) |πis a nonzero integer
2436 (cf. exercise 4.6.1<12), and there are multipoe
2443 factors modulo |εp |πi= |εp |πdivides the discriminant.
2451 (The factorization of (21) modulo 3 is (|εx|4α+↓|41)(x|g2|4α
2458 _↓|4x|4α_↓|41)|g2(x|g3|4α+↓|4x|g2|4α_↓|4x|4α+↓|41);
2459 |πsquared factors for this polynomial occur only
2466 for |εp|4α=↓|43, 23, 233 |πand 121702457. It
2473 is not di∃cult to prove that the smallest prime
2482 which is not unlucky is at most |εO(n|4|πlog|4|εNn),
2490 |πif |εn|4α=↓|4|πdeg(|εu) |πand |εN |πbounds
2495 the coe∃cients of |εu(x).)|'{A12}|πCOMP: PLEASE
2501 PUT NUMBER 18 IN CORRECT POSITION|'{A6}|≡1|≡8.|9|4(a)
2508 pp{H11}({H9}|εp|β1(u|βnx){H11}){H9}|4.|4.|4.|4|πpp{H11}({H9}
2508 |εp|βr(u|βnx){H11}){H9}, |πby Gauss's lemma.
2512 For example, let|'{A9}|εu(x)|4α=↓|46x|g3|4α_↓|43x|g2|4α+↓|42
2515 x|4α_↓|41,!!v(x)|4α=↓|4x|g3|4α_↓|43x|g2|4α+↓|412x|4α_↓|436|4
2515 α=↓|4(x|g2|4α+↓|412)(x|4α_↓|43);|;{A9}|πthen
2517 pp(|ε36x|g2|4α+↓|412)|4α=↓|43x|g2|4α+↓|41, |πpp(|ε6x|4α_↓|43
2518 )|4α=↓|42x|4α_↓|41. (|πThis is a modern version
2524 of a fourteenth-century trick used for many years
2532 to help solve algebraic equations.)|'!!|1|1(b)
2538 Let pp{H11}({H9}|εw(u|βnx){H11}){H9}|4α=↓|4|=3w|βmx|gm|4α+↓|
2539 4αo↓|4αo↓|4αo↓|4α+↓|4|=3w|β0|4α=↓|4w(u|βnx)/c,
2540 |πwhere |εc |πis the content of |εw(u|βnx) |πas
2548 a polynomial in |εx. |πThen |εw(x)|4α=↓|4(c|=3w|βm/u|urm|)n|
2553 )|4α+↓|4αo↓|4αo↓|4αo↓|4α+↓|4c|=3w|β0, |πhence
2555 |εc|=3w|βm|4α=↓|4u|urm|)n|); |πsince |ε|=3w|βm
2558 |πis a divisor of |εu|βn, c |πis a multiple of
2568 |εu|urmα_↓1|)n|).|'|Hu*?{U31}TEAM|91|'{H9L11M29}W58320#Comput
folio 818 galley 4
2570 er Programming|9(Knuth/Addison-Wesley)|9Answers|9f.|4818|9g.
2571 |44d|'{A6}|≡2|≡4|≡.|9|4|πMultiply a monic polynomial
2576 with rational coe∃cients by a suitable nonzero
2583 integer, to get a primitive polynomial over the
2591 integers. Factor this polynomial over the integers,
2598 and then convert the factors back to monic. (No
2607 factorizations are lost in this way; see exercise
2615 4.6.1<8.)|'{A3}|≡2|≡5|≡.|9|4Consideration of
2618 the constant term shows there are no factors
2626 of degree 1, so if the polynomial is reducible,
2635 it must have one factor of degree 2 and one of
2646 degree 3. Modulo 2 the factors are |εx(x|4α+↓|41)|g2(x|g2α+↓
2653 xα+↓1); |πthis is not much help. Modulo 3 the
2662 factors are (|εx|4α+↓|42)|g2(x|g3α+↓2xα+↓2).
2665 |πModulo 5 they are (|εx|g2|4α+↓|4x|4α+↓|41)(x|g3|4α+↓|44x|4
2669 α+↓|42). |πSo we see that the answer is (|εx|g2|4α+↓|4x|4α+↓
2677 |41)(x|g3|4α_↓|4x|4α+↓|42).|'{A3}|≡2|≡6|≡.|9|4|πBegin
2679 with |εD|2|3|¬L|5(0|4.|4.|4.|40|41), |πrepresenting
2682 the set |¬T0|¬Y. Then for 1|4|¬E|4|εj|4|¬E|4r,
2688 |πset |εD|5|¬L|5D|4|↔I|4(D |πshifted left |εd|βj),
2693 |πwhere |→|↔I denotes logical ``or.'' (Actually
2699 we need only |"p(|εn|4α+↓|41)/2|"P |πbits, since
2705 |εn|4α_↓|4j |πis in the set i= |εj |πis.)|'{A3}|≡2|≡7|≡.|9|4
2713 |πExercise 4 says that a random polynomial of
2721 degree |εn |πis irreducible modulo |εp |πwith
2728 rather low probability, about |ε1/n. |πBut the
2735 Chinese remainder theorem implies that a random
2742 monic polynomial of degree |εn |πover the integers
2750 will be reducible with respect to each of |εk
2759 |πdistinct primes with probability about (|ε1|4α_↓|41/n)|gk,
2764 |πand this approaches zero as |εk|5|¬M|5|→|¬X.
2771 |πHence almost all polynomials over the integers
2778 are irreducible with respect to in_nitely many
2785 primes; and almost all primitive polynomials
2791 over the integers are irreducible. [Another proof
2798 has been given by W. S. Brown, |εAMM |≡7|≡0 (1963),
2808 965<969.]|'{A3}|≡2|≡8|≡.|9|4False, we lose all
2813 |εp|βj |πwith |εe|βj |πdivisible by |εp. |πTrue
2820 if |εp|4|¬R|4|πdeg(|εu).|'{A3}|π|≡2|≡9|≡.|9|4Compute
2823 |εV|β1(x)|4α=↓|4|πgcd{H11}({H9}v(x),|4v|¬S(x){H11}){H9};
2824 |πthis is legitimate since |εv|β1(x) |πis relatively
2831 prime to |εv|¬S(x)/v|β1(x). |πLet |εv|β0(x)|4α=↓|4v(x)/v|β1(
2835 x), |πthe (squarefree) product of all irreducible
2842 factors of |εv(x). |πCompute |εd|β1(x)|4α=↓|4|πgcd{H11}({H9}
2846 u(x),|4v|β0(x){H11}){H9} |πand |εu|β1(x)|4α=↓|4u(x)/d|β1(x).
2848 |πIf deg(|εd|βj)|4|¬Q|40 |πfor |εj|4|¬R|41,
2853 |πcompute |ε|=∩d|βj|βα+↓|β1(x)|4α=↓|4|πgcd{H11}({H9}|εd|βj(x
2854 ),|4v|βj(x){H11}){H9}, d|βj|βα+↓|β1(x)|4α=↓|4|πgcd{H11}({H9}
2855 |ε|=∩d|βj|βα+↓|β1(x),|4u|βj(x){H11}){H9}, v|βj|βα+↓|β1(x)|4α
2856 =↓|4v|βj(x)/|=∩d|βj|βα+↓|β1(x), u|βj|βα+↓|β1(x)|4α=↓|4u|βj(x
2857 )/d|βj|βα+↓|β1(x); |πbut if deg(|εd|β1)|4α=↓|40,
2861 |π{H9}terminate the computation with the answer
2867 |εd(x)|4α=↓|4d|β1(x)|4.|4.|4.|4d|βj(x). {H11}({H9}|πIn
2869 this method, |εd|βj(x) |πis the squarefree product
2876 of all irreducible factors that occur |ε|→|¬Rj
2883 |πtimes in gcd({H9}|εu(x),|4v(x)){H9}. |πThere
2887 are several ways to avoid redundant calculations;
2894 for example, the same |εp |πcan be used in the
2904 underlying gcd computations, and the gcd routine
2911 should return the values of |εu(x)/d(x) |πand
2918 |εv(x)/d(x) |πthat it computes. Furthermore the
2924 computation is unsymmetric in |εu |πand |εv;
2931 |πit seems better to interchange the r|=7oles
2938 of |εu |πand |εv |πif deg(|εu)|4|¬Q|4|πdeg(|εv)
2944 |πat the beginning or if deg(|εu|βj)|4|¬Q|4|πdeg(|εv|βj)
2950 |πwhen computing |εd|βj|βα+↓|β1(x).{H11}){H9}|'
2953 {A3}|≡3|≡0|≡.|9|4|πCf. exercise 4; the probability
2958 is the coe∃cient of |εz|gn |πin (|ε1α+↓a|β1|βpz/p)|→|6α⊗↓>
2965 (1|3α+↓|3|εa|β2|βpz|g2/p|g2)(1|3α+↓|3a|β3|βpz|g3/p|g3)|4.|4.
2965 |4.|4, |πwhich has the limiting value |εg(z)|3α=↓|3(1|3α+↓|3
2971 |εz)(1|3α+↓|3|f1|d32|)z|g2)|→|5α⊗↓>(|ε1|4α+↓|4|f1|d33|)z|g3)
2972 . |πFor |ε1|4|¬E|4n|4|¬E|410 |πthe answers are
2978 1, |f1|d32|), |f5|d36|), |f7|d312|), |f37|d360|),
2983 |f79|d3120|), |f173|d3280|), |f101|d3168|), |f127|d3210,
2987 |f1033|d31680|). {H11}({H9}|πLet>|εf(y)|4α=↓|4|πln(|ε1|4α+↓|
2989 4y)|4α_↓|4y|4α=↓|4O(y|g1). |πNow |εg(z)|4α=↓|4|πexp{H11}({H9
2991 }|¬K|ε|βn|β|¬R|β1|4z|gn/n|4α+↓|4|¬K|βn|β|¬R|β1|4f(z|gn/n){H1
2991 1}){H9}|6|→α=↓>|εh(z)/(1|4α_↓|4z), |πnow it can
2996 be shown that the limiting probability is |εh(1)|6|→α=↓>
3004 |πexp{H11}({H9}|ε|¬K|βn|β|¬R|β1|4f(1/n){H11}){H9}α=↓e|gα_↓|g
3004 |≤g|4|¬V|4.56146 |πas |εn|5|¬M|5|→|¬X [|πcf.
3008 D. H. Lehmer, |εActa Arith. |π|≡2|≡1 (1972),>
3015 |π379<388]. Indeed, N. G. de Bruijn has established
3023 the asymptotic formula lim|ε|βp|β|¬M|β|¬X|3a|βn|βp|6|→α=↓>
3027 e|gα_↓|g|≤g|4α+↓|4e|gα_↓|g|≤g/n|4α+↓|4O(n|gα_↓|g2).|'
3028 {A24}{H10L12}|∨S|∨E|∨C|∨T|∨I|∨O|∨N|9|∨4|∨.|∨6|∨.|∨3|'
3029 {A12}{H9L11}|5|5|≡1|≡.|9|4|ε2|g|≤l|g(|gn|g),
3030 |πthe highest power of 2 less than or equal to
3040 |εn.|'{A3}|π|5|5|≡2|≡.|9|4Assume that |εx |πis
3045 input in register A, and |εn |πin location |¬n|¬n;
3054 the output is in register X.|'{A6}!!!|*/|↔c|↔O!!|\|¬a|¬1!|¬e|
3060 ¬n|¬t|¬x!|¬1|5|6!!|h|εL|4α+↓|4|n1|h|4α_↓|4K!|nA|*/|↔O|\.|4|4I
3060 nitialize.|'!!!|*/|↔c|↔P!!!|4!|\|¬s|¬t|¬x|5|6!|¬y|5|6!!|hL|4α
3061 +↓|4|n1|h|4α_↓|4K!!|nY|5|¬L|51.|'!!!|*/|↔c|↔L!!|\!|4!|¬s|¬t|¬
3062 a|5|6!|¬z!!|hL|4α+↓|4|n1|h|4α_↓|4K!!|nZ|5|¬L|5x.|'
3063 !!!|*/|↔c|↔M|\!!!|4!|¬l|¬d|¬a|5|6!|¬n|¬n!!|hL|4α+↓|4|n1|h|4α_
3063 ↓|4K!!|nN|5|¬L|5n.|'!!!|*/|↔c|↔C|\!!!|4!|¬j|¬m|¬p|5|6!|¬2|¬f!
3064 !|hL|4α+↓|4|n1|h|4α_↓|4K!!|n|πTo|6A2.|'!!!|ε|*/|↔c|↔o|\!!|¬5|
3065 ¬h!|¬s|¬r|¬b|5|6|¬1|5|6!!L|4α+↓|41|4α_↓|4K!!|'
3066 !!!|*/|↔c|↔p!!|\!|4!|¬s|¬t|¬a|5|6!|¬n|5|6!!L|4α+↓|41|4α_↓|4K!
3066 !N|5|¬M|5|"lN/2|"L.|'!!!|*/|↔c|↔l|\!!|π|¬a|¬5!|¬l|¬d|¬a|5|6!|
3067 ¬z|5|6!!|hL|4α+↓|3|n|εL|h|3α_↓|4K!!|nA|*/|↔C|6|\Square|6Z.|'
3068 !!!|*/|↔c|↔m|\!!!|4!|π|¬m|¬u|¬l|5|6!|¬z|5|6!!|h|εL|4α+↓|3|nL|
3068 h|3α_↓|4K!!|nZ|4α⊗↓|4Z|'!!!|ε|*/|↔O|↔c|\!!!|4!|π|¬s|¬t|¬x|5|6
3069 !|¬z|5|6!!|h|εL|4α+↓|3|nL|h|3α_↓|4K!!|n!|¬M|5Z.|'
3070 !!!|*/|↔O|↔O|\!!|π|¬a|¬2!|¬l|¬d|¬a|5|6|¬n|5|6!!|h|εL|4α+↓|3|n
3070 L|h|3α_↓|4K!!|nA|*/|↔P|\.|4|4Halve|6N.|'!!!|*/|↔O|↔P!!|\|π|¬2|
3071 ¬h!|¬j|¬a|¬e|5|6!|¬5|¬b!!|h|ε|2α_↓|nL|4α+↓|41|h|6K!!|n|πTo|6
3071 A5|6if|6|εN|6|πis|6even.|'!!!|*/|↔O|↔L!!!|4!|\|π|¬s|¬r|¬b|5|6
3072 !|¬1|5|6!!|h|εL|7α+↓|nK|h|91α+↓|n|'!!!|*/|↔O|↔M!!|\!|4!|π|¬s|
3073 ¬t|¬a|5|6!|¬n|5|6!!|h|ε|7Lα+↓|nK|h|91α+↓!!|nN|5|¬M|5|"lN/2|"
3073 L.|'!!!|*/|↔O|↔C|\!!|π|¬a|¬3!|¬l|¬d|¬a|5|6!|¬z|5|6!!|h|εL|7α+
3074 ↓|nK|h1|9α+↓!!|nA|*/|↔L|\.|4|4Multiply|6Y|6by|6Z.|'
3075 !!!|*/|↔O|↔o!!!|4|\!|π|¬m|¬u|¬l|5|6!|¬y|5|6!!|h|εL|7α+↓|nK|h1
3075 |9α+↓!!|nZ|4α⊗↓|4Y|'!!!|*/|↔O|↔p|\!!!|4!|π|¬s|¬t|¬x|5|6!|¬y|5
3076 |6!!|h|εL|7α+↓|nK|h1|9α+↓!!!!|n|¬M|5Y.|'!!!|*/|↔O|↔l|\!!|π|¬a
3077 |¬4!|¬l|¬d|¬a|5|6!|¬n|5|6!!|h|εL|7α+↓|nK|h1|9α+↓!!|nA|*/|↔M|\
3077 .|4|4N|4α=↓|4|*/|↔c?|'!!!|↔O|↔m!!|\!|4!|π|¬j|¬a|¬p|5|6!|¬a|¬5
3078 !!|h|εL|7α+↓|nK|h1|9α+↓!!|n|πIf|6not,|6continue|6at|6step|6A
3078 5.|'{A6}{H9L11}{H11}({H9}|πIt would be better
3083 programming practice to change the instruction
3089 in line 05 to ``|¬j|¬a|¬p'', followed by an error
3098 indication. The running time is |ε21L|4α+↓|417K|4α+↓|413,
3104 |πwhere |εL|4α=↓|4|≤l(n) |πis one less than the
3111 number of bits in the binary representation of
3119 |εn, |πand |εK|4α=↓|4|≤n(n) |πis the number of
3126 one bits in |εn'|πs representation. The running
3133 time could be decreased by |εK|4α+↓|46 |πunits,
3140 by inserting step A4 before step A3 and adding
3149 two new instructions to perform A3 when |εN|4α=↓|40.{H11}){H
3156 9}|'!!|2|πFor the serial program, we may assume
3164 that |εn |πis small enough to _t in an index
3174 register; otherwise serial exponentiation is
3179 out of the question. The following program leaves
3187 the output in register A:|'{A6}!!!!!|9|π|¬s|¬1!|¬l|¬d|¬1|5|6
3192 !|¬n|5|6!!|h|εN|6|n1!|4|πrI1|5|¬M|5|εn.|'!!!!!|9!|4!|π|¬s|¬t
3193 |¬a|5|6!|¬x|5|6!!|h|εN|6|n1!|4|εX|5|¬M|5x.|'|π!!!!!|9!|4!|¬j
3194 |¬m|¬p|5|6!|¬2|¬f!!|h|εN|6|n1!|4|'!!!!!|9|π|¬1|¬h!|¬m|¬u|¬l|
3195 5|6!|¬x|5|6!!|εN|4α_↓|41!!|πrA|4α⊗↓|4X|'!!!!!|9!|4!|π|¬s|¬l|
3196 ¬a|¬x!|¬5!!|εN|4α_↓|41!!!!|6|¬M|5|πrA.|'!!!!!|9|¬2|¬h!|¬d|¬e
3197 |¬c|¬1!|¬1|5|6!!|n|9|5|5|εN|9|5|5!!|πrI1|5|¬M|5rI1|4α_↓|41.|
3197 '!!!!!|9!|4!|π|¬j|¬1|¬p|5|6!|¬1|¬b!!|9|5|5|εN|9|5|5!!|πMulti
3198 ply|6again|6if|6rI1|4|¬Q|40.|'{A6}{H9L11M29}|πThe
3200 running time for this program is |ε14N|4α_↓|47;
3207 |πit is faster than the previous program when
3215 |εn|4|¬R|47, |πslower when |εn|4|¬R|48.|'|π|5|5|≡3|≡.|9|4|πT
3219 he sequences of e ponents are: (a) 1, 2, 3, 6,
3230 7, 14, 15, 30, 60, 120, 121, 242, 243, 486, 487,
3241 974, 974 [16 multiplications]; (b) 1, 2, 3, 4,
3250 8, 12, 24, 36, 72, 108, 216, 324, 325, 650, 975
3261 [14 multiplications]; (c) 1, 2, 3, 6, 12, 15,
3270 30, 60, 120, 240, 243, 486, 972, 975 [13 multiplications];
3280 (d) 1, 2, 3, 6, 13, 15, 30, 60, 75, 150, 225,
3292 450, 900, 975 [13 multiplications]. {H11}({H9}The
3298 fewest possible number of multiplications is
3304 12; this is obtainable by combining the factor
3312 method with the binary method, since 975|4α=↓15|4|¬O|4(2|g6|
3318 4α+↓|41).{H11}){H9}|'|5|5|≡4|≡.|9|4(777777)|β8|4α=↓|42|g1|g8
3319 |4α_↓|41.|'{A3}{I3.3H}|5|5|≡5|≡.|9|4|≡T|≡1|≡.|9|4[Initialize
3320 .] Set |¬l|¬i|¬n|¬k|¬u[|εj]|π|5|¬M|50 for |ε1|4|¬E|4j|4|¬E|4
3324 2|gr, |πand set |εk|5|¬M|50, |π|¬l|¬i|¬n|¬k|¬r[0]|5|¬M|51,
3329 |¬l|¬i|¬n|¬k|¬r[1]|5|¬M|50.|'{A3}!!|2|≡T|≡2|≡.|9|4Change
3331 level.] (Now level |εk |πof the tree has been
3340 linked together from left to right, starting
3347 at |¬l|¬i|¬n|¬k|¬r[0].) If |εk|4α=↓|4r, |πthe
3352 algorithm terminates. Otherwise set |εn|5|¬M|5|π|¬l|¬i|¬n|¬k
3356 |¬r[0], |εm|5|¬M|50.|'{A3}!!|2|π|≡T|≡3|≡.|9|4[Prepare
3359 for |εn.] (|πNow |εn |πis a node on level |εk,
3369 |πand |εm |πpoints to the rightmost node currently
3377 on level |εk|4α+↓|41.) |πSet |εq|5|¬L|50, s|5|¬L|5n.|'
3383 {A3}!!|2|π|≡T|≡4|≡.|9|4[|πAlready in tree?] (Now
3387 |εs |πis a node in the path from the root to
3398 |εn.) |πIf |¬l|¬i|¬n|¬k|¬u[|εn|4α+↓|4s]|π|4|=|↔6α=↓|40,
3401 go to T6 (the value |εn|4α+↓|4s |πis already
3409 in the tree).|'{A3}!!|2|≡T|≡5|≡.|9|4[Insert below
3414 |εn.] |πIf |εq|4α=↓|40, |πset |εm|¬S|5|¬L|5n|4α+↓|4s.
3419 |πSet |¬l|¬i|¬n|¬k|¬r[|εn|4α+↓|4s]|5|¬L|5q, |π|¬l|¬i|¬n|¬k|¬
3421 u[|εn|4α+↓|4s]|5|¬L|5n, q|5|¬L|5n|4α+↓|4s.|'{A3}!!|2|π|≡T|≡6
3423 |≡.|9|4[Move up.] Set |εs|5|¬L|5|π|¬l|¬i|¬n|¬k|¬u[|εs].
3427 |πIf |εs|4|=|↔6α=↓|40, |πreturn to T4.|'{A3}!!|2|≡T|≡7|≡.|9|
3432 4[Attach group.] If |εq|4|=|↔6α=↓|40, |πset |¬l|¬i|¬n|¬k|¬r[
3437 |εm]|5|¬L|5q, m|5|¬L|5m|¬S.|'{A3}!!|2|π|≡T|≡8|≡.|9|4[Move
3440 |εn.] |πSet |εn|5|¬L|5|π|¬l|¬i|¬n|¬k|¬r[|εn].
3443 |πIf |εn|4|=|↔6α=↓|40, |πreturn to T3.|'{A3}!!|2|≡T|≡9|≡.|9|
3448 4[End of level.] Set |¬l|¬i|¬n|¬k|¬r[|εm]|5|¬L|50,
3453 k|5|¬L|5k|5α+↓|51, |πand return to T2.|'{A3}{IC}|5|5|≡6|≡.|9
3458 |4Prove by induction that the path to the number
3467 |ε2|ge|r0|4α+↓|42|ge|r1|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|42|ge|rt,
3468 |πif |εe|β0|4|¬Q|4e|β1|4|¬Q|4|¬O|4|¬O|4|¬O|4|¬Qe|βt|4|¬R|40,
3469 |πis |ε1, 2, 2|g2,|4.|4.|4.|4,|42|ge|r0, 2|ge|r0|4α+↓|42|ge
3474 |r1, .|4.|4.|4, 2|ge|m0|4α+↓|42|ge|r1|4α+↓|4|¬O|4|¬O|4|¬O|4α
3476 +↓|42|ge|rt; |πfurthermore, the sequence of exponents
3482 on each level are in decreasing lexicographic
3489 order.|'{A3}|5|5|≡7|≡.|9|4The binary and factor
3494 methods require one more step to compute |εx|g2|gn
3502 |πthan |εx|gn; |πthe power tree method requires
3509 at most one more step. hence (a) 15|4|¬O|42|ε|gk;
3517 (|πb) 33|4|¬O|4|ε2|gk; (|πc) 23|4|¬O|4|ε2|gk;
3521 k|4α=↓|40, 1, 2, 3,|4.|4.|4.|4.|'{A3}|5|5|≡8|≡.|9|4|πThe
3526 power tree always includes the node |ε2m |πat
3534 one level below |εm, |πunless it occurs at the
3543 same level or an earlier level; and it always
3552 includes the node |ε2m|4α+↓|41 |πat one level
3559 below |ε2m, |πunless it occurs at the same level.
3568 (Computational experiments have shown that |ε2m
3574 |πis below |εm |πfor all |εm|4|¬E|4|π2000, but
3581 it appears very di∃cult to prove this in general.)|'
3590 {A3}|≡1|≡0|≡.|9|4By using the ``|¬f|¬a|¬t|¬h|¬e|¬r''
3594 representation discussed in Section 2.3.3: Make
3600 use of a table |εf[j], 1|4|¬E|4J|4|¬E|4100, |πsuch
3607 that |εf[1]|4α=↓|40 |πand |εf[j] |πis the number
3614 of the node just above |εj |πfor |εj|4|¬R|42.
3622 (|πThe fact that each node of this tree has degree
3632 at most two has no e=ect on the e∃ciency of this
3643 representation; it just makes the tree look prettier
3651 as an illustration.)|'{A3}|≡1|≡1|≡.|9|41, 2,
3656 3, 5, 10, 20, (23 or 40), 43; 1, 2, 4, 8, 9,
3669 17, (26 or 34), 43; 1, 2, 4, 8, 9, 17, 34, (43
3682 or 68), 77; 1, 2, 4, 5, 9, 18, 36, (41 or 72),
3695 77. If either of the latter two paths were in
3705 the tree we would have no possibility for |εn|4α=↓|443,
3714 |πsince the tree must contain either 1, 2, 3,
3723 5 or 1, 2, 4, 8, 9.|'{A3}|≡1|≡2|≡.|9|4No such
3732 in_nite tree can exist since |εl(n)|4|=|↔6α=↓|4l|≤⊂(n)
3738 |πfor some |εn.|'|Hβ*?*?*?*?{U0}{H9L11M29}|πW58320#Computer|4Pro
folio 821 galley 5
3741 gramming!(Knuth/Addison-Wesley)!Answers!f.|4821!g.|45d|'
3742 {A6}|≡1|≡3|≡.|9|4For Case 1, use a Type-1 chain
3749 followed by |ε2|gA|gα+↓|gC|4α+↓|42|gB|gα+↓|gC|4α+↓|42|gA|4α+
3751 ↓|42|gB; |πor use the factor method. For Case
3759 2, use a Type-2 chain followed by 2|ε|gA|gα+↓|gC|gα+↓|g1|4α+
3766 ↓|42|gB|gα+↓|gC|4α+↓|42|gA|4α+↓|42|gB. |πFor
3768 Case 3, use a Type-5 chain followed by addition
3777 of |ε2|gA|4α+↓|42|gA|gα_↓|g1, |πor use the factor
3783 method. For Case 4, |εn|4α=↓|4135|4αo↓|42|gD,
3788 |πso we may use the factor method.|'{A3}|≡1|≡4|≡.|9|4a)|9It
3796 is easy to verify that steps |εr|4α_↓|41 |πand
3804 |εr|4α_↓|42 |πare not both small, so let us assume
3813 that step |εr|4α_↓|41 |πis small and step |εr|4α_↓|42
3821 |πis not. If |εc|4α=↓|41, |πthen |ε|≤l(a|βr|βα_↓|β1)|4α=↓|4|
3826 ≤l(a|βr|βα_↓|βk), |πso |εk|4α=↓|42; |πand since
3831 |ε4|4|¬E|4|≤n(a|βr)|4α=↓|4|≤n(a|βr|βα_↓|β1)|4α+↓|4|≤n(a|βr|β
3831 α_↓|βk)|4α_↓|41|4|¬E|4|≤n(a|βr|βα_↓|β1)|4α+↓|41,
3832 |πwe have |ε|≤n(a|βr|βα_↓|β1)|4|¬R|43, |πmaking
3836 |εr|4α_↓|41 |πa star step (lest |εa|β0, a|β1,|4.|4.|4.|4,
3843 a|βr|βα_↓|β3, a|βr|βα_↓|β1 |πinclude only one
3848 small step). Then |εa|βr|βα_↓|β1|4α=↓|4a|βr|βα_↓|β2|4α+↓|4a|
3851 βr|βα_↓|βq |πfor some |εq, |πand if we replace
3859 |εa|βr|βα_↓|β2, a|βr|βα_↓|β1, a|βr |πby |εa|βr|βα_↓|β2,
3864 2a|βr|βα_↓|β2, 2a|βr|βα_↓|β2|4α+↓|4a|βr|βα_↓|βq|4α=↓|4a|βr,
3866 |πwe obtain another counterexample chain in which
3873 step |εr |πis small; but this is impossible.
3881 On the other hand, if |εc|4|¬R|42, |πthen 4|4|¬E|4|ε|≤n(a|βr
3888 )|4|¬E|4|≤n(a|βr|βα_↓|β1)|4α+↓|4|≤n(a|βr|βα_↓|βk)|4α_↓|42|4|
3888 ¬E|4|≤n(a|βr|βα_↓|β1); |πhence |ε|≤n(a|βr|βα_↓|β1)|4α=↓|44,
3891 |≤n(a|βr|βα_↓|βk)|4α=↓|42, |πand |εc|4α=↓|42.
3894 |πThis leads readily to an impossible situation
3901 by a consideration of the six types in the proof
3911 of Theorem B.|'!!|1|1b)|9If |ε|≤l(a|βr|βα_↓|βk)|4|¬W|4m|4α_↓
3915 |41, |πwe have |εC|4|¬R|43, |πso |ε|≤n(a|βr|βα_↓|βk)|4α+↓|4|
3920 ≤n(a|βr|βα_↓|β1)|4|¬R|47 |πby (22); therefore
3924 both |ε|≤n(a|βr|βα_↓|βk) |πand |ε|≤n(a|βr|βα_↓|β1)
3928 |πare |→|¬R3. |πAll small steps must be |ε|→|¬Er|4α_↓|4k,
3936 |πand |ε|≤l(a|βr|βα_↓|βk)|4α=↓|4m|4α_↓|4k|4α+↓|41.
3938 |πIf |εk|4|¬R|44, |πwe must have |εc|4α=↓|44,
3944 k|4α=↓|44, |≤n(a|βr|βα_↓|β1)|4α=↓|4|≤n(a|βr|βα_↓|β4)|4α=↓|44
3945 ; |πthus |εa|βr|βα_↓|β1|4|¬R|42|gm|4α+↓|42|gm|gα_↓|g1|4α+↓|4
3947 2|gm|gα_↓|g2, |πand |εa|βr|βα_↓|β1 |πmust equal
3952 |ε2|gm|4α+↓|41|gm|gα_↓|g1|4α+↓|42|gm|gα_↓|g2|4α+↓|42|gm|gα_↓
3952 |g3; |πbut |εa|βr|βα_↓|β4|4|¬R|4|f1|d38|)a|βr|βα_↓|β1
3955 |πnow implies that |εa|βr|βα_↓|β1|4α=↓|48a|βr|βα_↓|β4.
3959 |πThus |εk|4α=↓|43 |πand |εa|βr|βα_↓|β1|4|¬Q|42|gm|4α+↓|42|g
3962 m|gα_↓|g1. |πSince |εa|βr|βα_↓|β2|4|¬W|42|gm
3965 |πand |εa|gr|gα_↓|g3|4|¬W|42|gm|gα_↓|g1, |πstep
3968 |εr|4α_↓|41 |πmust be a doubling; but step |εr|4α_↓|42
3976 |πis a nondoubling, since |εa|βr|βα_↓|β1|4|=|↔6α=↓|44a|βr|βα
3980 _↓|β3. |πFurthermore, since |ε|≤n(a|βr|βα_↓|β3)|4|¬R|43,
3984 r|4α_↓|43 |πis a star step; and |εa|βr|βα_↓|β2|4α=↓|4a|βr|βα
3990 _↓|β3|4α+↓|4a|βr|βα_↓|β5 |πwould imply that |εa|βr|βα_↓|β5|4
3994 α=↓|42|gm|gα_↓|g2, |πhence we must have |εa|βr|βα_↓|β2|4α=↓|
3999 4a|βr|βα_↓|β3|4α+↓|4a|βr|βα_↓|β4. |πAs in a similar
4004 case treated in the text, the only possibility
4012 is now seen to be |εa|βr|βα_↓|β4|4α=↓|42|gm|gα_↓|g2|4α+↓|42|
4017 gm|gα_↓|g3, a|βr|βα_↓|β3|4α=↓|42|gm|gα_↓|g2|4α+↓|42|gm|gα_↓|
4018 g3|4α+↓|42|gd|gα+↓|g1|4α+↓|42|gd, a|βr|βα_↓|β1|4α=↓|42|gm|4α
4019 +↓|42|gm|gα_↓|g1|4α+↓|42|gd|gα+↓|g2|4α+↓|42|gd|gα+↓|g1,
4020 |πand even this possibility is impossible.|'{A3}|≡1|≡6|≡.|9|
4026 4|λ3|ε|gB(n)|4α=↓|4|≤l(n)|4α+↓|4|≤n(n)|4α_↓|41;
4027 |πso if |εn|4α=↓|42|gk, |λ3|gB(n)/|≤l(n)|4α=↓|41,
4031 |πbut if |εn|4α=↓|42|gk|gα+↓|g1|4α_↓|41, |λ3|gB(n)/|≤l(n)|4α
4034 =↓|42.|'{A3}|≡1|≡7|≡.|9|4|πLet |εi|β1|4|¬W|4αo↓|4αo↓|4αo↓|4|
4036 ¬W|4i|βt. |πDelete any intervals |εI|βk |πwhich
4042 can be removed without a=ecting the union |εI|β1|4|↔q|4αo↓|4
4049 αo↓|4αo↓|4|↔q|4I|βt. (|πThe interval (|εj|βk,|4i|βk]
4053 |πmay be dropped out if either |εj|βk|βα+↓|β1|4|¬E|4j|βk
4060 |πor |εj|β1|4|¬W|4j|βk |πor |εj|β1|4|¬W|4j|β2|4|¬W|4αo↓|4αo↓
4063 |4αo↓ |πand |εj|βk|βα+↓|β1|4|¬E|4i|βk|βα_↓|β1.)
4066 |πNow combine overlapping intervals (|εj|β1,|4i|β1],|4.|4.|4
4070 .|4,|4(j|βd,|4i|βd] |πinto an interval (|εj|1|¬S,|4i|¬S]|4α=
4074 ↓|4(j|β1,|4i|βd] |πand note that|'{A6}{A3}|εa|βi|β|¬S(1|4α+↓
4078 |4|≤d)|gi|r1|iα_↓|ij|r1|gα+↓|1|gαo↓|1|gαo↓|1|gαo↓|1|gα+↓|gi|
4078 rd|gα_↓|gj|rd|4|¬E|4a|βj|β|¬S(1|4α+↓|4|≤d)|g2|g(|gi|g|¬S|gα_
4078 ↓|gj|g|¬S),|;{A9}|πsince each point of (|εj|1|¬S,|4i|¬S]
4084 |πis covered at most twice in (|εj|βi,|4i|β1]|4|↔q|4αo↓|4αo↓
4090 |4αo↓|4|↔q|4(j|βd,|4i|βd].|'{A3}|π|≡1|≡8|≡.|9|4Call
4092 |εf(m) |πa ``nice'' function|=|ε|gm|¬H|v4f(m)|)|4|¬M|41
4096 |πas |εm|4|¬M|4|¬X, |πthat is, {H11}({H9}log|4|εf(m){H11}){H
4100 9}/m|4|¬M|40. |πA polynomial in |εm |πis nice.
4107 The product of nice functions is nice. If |εg(m)|4|¬M|40
4116 |πand |εc |πis a positive constant, then |εc|gm|gg|g(|gm|g)
4124 |πis nice; also (|ε|f2m|d5mg(m)|) |πis nice,
4130 for by Stirling's approximation this is equivalent
4137 to saying that |εg(m)|4|πlog{H11}({H9}|ε1/g(m){H11}){H9}|4|¬
4140 M|40.|'{A3}!!|1|1|πNow replace each term of the
4147 summation by the maximum term which is attained
4155 for any |εs, t, v. |πThe total number of terms
4165 is nice, and so are (|ε|fmα+↓s|d5tα+↓v|)), (|ftα+↓v|d5v|))|4
4171 |¬E|42|gt|gα+↓|gv, |πand |ε|≤b|g2|rv, |πbecause
4175 (|εt|4α+↓|4v)/m|4|¬M|40. |πFinally, (|ε|f(mα+↓s)|i2|d5t|))|4
4177 |¬E|4(2m)|g2|gt/t*3|4|¬W|4(4m|g2/t)|gte|gt, |πwhere
4179 (|ε4e)|gt |πis nice; setting |εt |πto its maximum
4187 value (1|4α_↓|4|ε|f1|d32|)|≤e)m/|≤l(m), |πwe
4190 have |ε(m|g2/t)|gt|4α=↓|4({H11}(m|≤l(m)/(1|4α_↓|4|f1|d32|)|≤
4191 e){H11}){H9}|gt|4α=↓|42|gm|g(|g1|gα_↓|g|≤e|g/|g2|g)|4αo↓|4f(
4191 m), |πwhere |εf(m) |πis nice. Hence the entire
4199 sum is less than |ε|≤a|gm |πfor large |εm, |πif
4208 |ε|≤a|4α=↓|42|g1|gα_↓|g|≤h, 0|4|¬W|4|≤h|4|¬W|4|f1|d32|)|≤e.|
4209 '{A3}|≡1|≡9|≡.|9|4|πa)|9|1|εM|4|↔Q|4N, M|4|↔q|4N,
4212 M|4|=|rα+↓|↔q|4N, |πrespectively; see Eqs. 4.5.2<6,
4217 4.5.2<7.|'!!|1|1b)|9|εf(z)g(z), |πlcm{H11}({H9}|εf(z),|4g(z)
4219 {H11}){H9}, |πgcd{H11}({H9}|εf(z),|4g(z){H11}){H9}.
4221 (|πFor the same reasons as (a), because the monic
4230 irreducible polynomials over the complex numbers
4236 are precisely the polynomials |εz|4α_↓|4|≤z.)|'
4241 !!|1|1|πc)|9Commutative laws |εA|4|"b|4B|4α=↓|4B|4|"b|4A,
4244 A|4|↔q|4B|4α=↓|4B|4|↔q|4A, A|4|↔Q|4B|4α=↓|4B|4|↔Q|4A.
4246 |πAssociative laws |εA|4|"b|4(B|4|"b|4C)|4α=↓|4(A|4|"b|4B)|4
4248 |"b|4C, A|4|↔q|4(B|4|↔q|4C)|4α=↓|4(A|4|↔q|4B)|4|↔q|4C,
4250 A|4|↔Q|4(B|4|↔Q|4C)|4α=↓|4(A|4|↔Q|4B)|4|↔Q|4C.
4251 |πDistributive laws |εA|4|↔q|4(B|4|↔Q|4C)|4α=↓|4(A|4|↔q|4B)|
4253 4|↔Q|4(A|4|↔q|4C), A|4|↔Q|4(B|4|↔q|4C)|4α=↓|4(A|4|↔Q|4B)|4|↔
4254 q|4(A|4|↔Q|4C), A|4|"b|4(B|4|↔q|4C)|4α=↓|4(A|4|"b|4B)|4|↔q|4
4255 (A|4|"b|4C), A|4|"b|4(B|4|↔Q|4C)|4α=↓|4(A|4|"b|4B)|4|↔Q|4(A|
4256 4|"b|4C). |πIdempotent laws |εA|4|↔q|4A|4α=↓|4A,
4260 a|4α=↓|4A. |πAbsorption laws |εA|4|↔q|4(A|4|↔Q|4B)|4α=↓|4A,
4264 A|4|↔Q|4(A|4|↔q|4B)|4α=↓|4A, A|4|↔Q|4(A|4|"b|4B)|4α=↓|4A,
4266 A|4|↔q|4(A|4|"b|4B)|4α=↓|4A|4|"b|4B. |πIdentity
4268 and zero laws |ε|9|1|4|"b|4A|4α=↓|4A, |9|1|4|↔q|4A|4α=↓|4A,
4273 |9|1|4|↔Q|4A|4α=↓|4|9|1, |πwhere |9|1 |πis the
4278 empty multiset. Counting law |εA|4|"b|4B|4α=↓|4(A|4|↔q|4B)|4
4282 |"b|4(A|4|↔Q|4B). |πFurther properties analogous
4286 to those of sets come from the partial ordering
4295 de_ned by the rule |εA|4|↔Y|4B |πi= |εA|4|↔Q|4B|4α=↓|4A
4302 (|πi= |εA|4|↔q|4B|4α=↓|4B).|'!!|1|1|*/Notes: |π|\Other
4306 common applications of multisets are zeros and
4313 poles of meromorphic functions, invariants of
4319 matrices in canonical form, invariants of _nite
4326 Abelian groups, etc.; multisets can be useful
4333 in combinatorial counting arguments and in the
4340 development of measure theory. The terminal strings
4347 of a noncircular context-Free grammar form a
4354 multiset which is a set if and only if the grammar
4365 is unambigous. Although multisets appear frequently
4371 in mathematics, they often must be treated rather
4379 clumsily because there is currently no standard
4386 way to treat sets with repeated elements. Several
4394 mathemaicians have voiced their belief that the
4401 lack of adequate terminology and notation for
4408 this common concept has been a de_nite handicap
4416 to the development of mathematics. (A multiset
4423 is, of course, formally equivalent to a mapping
4431 from a set into the nonnegative integers, but
4439 this formal equivalence is of little or no practical
4448 value for creative mathematical reasoning.) The
4454 author has discussed this matter with many people
4462 in an attempt to _nd a good remedy. some of the
4473 names suggested for the concept were list, bunch,
4481 heap, sample, weighted set, collection; but these
4488 words either con⊗ict with present terminology,
4494 have an improper connotation, or are too much
4502 of a mouthful to say and to write conveniently.
4511 It does not seem out of place to coin a new word
4523 for such an important concept, and ``multiset''
4530 has been suggested by N. G. de Bruijn. The notation
4540 ``|εA|4|"b|4B'' |πhas been selected by the author
4547 to avoid con⊗ict with existing notations and
4554 to stress the analogy with set union. It would
4563 not be as desirable to use ``|εA|4α+↓|4B'' |πfor
4571 this purpose, since algebraists have found that
4578 |εA|4α+↓|4B |πis a good notation for |¬T|ε|≤a|4α+↓|4|≤b|4|¬G
4584 |4|≤a|4|¬A|4A |πand |ε|≤b|4|¬A|4B|¬Y. |πIf |εA
4589 |πis a multiset of nonnegative integers, let
4596 |εG(z)|4α=↓|4|¬K|βn|β|¬A|βA|4z|gn |πbe a generating
4600 function corresponding to |εA. (|πGenerating
4605 functions with nonnegative integer coe∃cients
4610 obviously correspond one-to-one with multisets
4615 of nonnegative integers.) If |εG(z) |πcorresponds
4621 to |εA |πand |εH(z) |πto |εB, |πthen |εG(z)|4α+↓|4H(z)
4629 |πcorresponds to |εA|4|"b|4B |πand |εG(z)H(z)
4634 |πcorresponds to |εA|4α+↓|4B. |πIf we form ``Drichlet''
4641 generating functions |εg(z)|4α=↓|4|¬K|βn|β|¬A|βA|41/n|gz,
4644 h(z)|4α=↓|4|¬K|βn|β|¬A|βB|41/n|gz, |πthe product
4647 |εg(z)h(z) |πcorresponds to the multiset product
4653 |εAB.|'{A3}|π|≡2|≡0|≡.|9|4Type 3: (|εS|β0,|4.|4.|4.|4,|4S|βr
4656 )|4α=↓|4(M|β0|β0,|4.|4.|4.|4,|4M|βr|β0)|4α=↓|4(|¬T0|¬Y,|4.|4
4656 .|4.|4,|4|¬TA|¬Y, |¬TA|4α_↓|41,|4A|¬T, |¬TA|4α_↓|41,
4659 A,|4 A|¬Y, |¬TA|4α_↓|41, A|4α_↓|41, A, A, A|¬Y,|4.|4.|4.|4,
4666 |¬TA|4α+↓|4C|4α_↓|43, A|4α+↓|4C|4α_↓|42, A|4α+↓|4C|4α_↓|42,
4669 A|4α+↓|4C|4α_↓|42|¬Y). |πType 5: (|εM|β0|β0,|4.|4.|4.|4,
4673 M|βr|β0)|4α=↓|4(|¬T0|¬Y,|4.|4.|4.|4, |¬TA|¬Y,
4675 |¬TA|4α_↓|41, A|¬Y,|4.|4.|4.|4, |¬TA|4α+↓|4C|4α_↓|41,
4678 A|4α+↓|4C|¬Y, |¬Ta|4α+↓|4C|4α_↓|41, A|4α+↓|4C|4α_↓|41,
4681 A|4α+↓|4C|¬Y,|4.|4.|4.|4, |¬TA|4α+↓|4C|4α+↓|4D|4α_↓|41,
4683 A|4α+↓|4C|4α+↓|4D|4α_↓|41, A|4α+↓|4C|4α+↓|4D|¬Y),
4685 (M|β0|β1,|4.|4.|4.|4, M|βr|β1)|4α=↓|4(|9|1,|4.|4.|4.|4,|4|9|
4686 1, |9|1,|4.|4.|4.|4,|4|9|1, |¬TA|4α+↓|4C|4α_↓|42|¬Y,|4.|4.|4
4688 .|4, |¬TA|4α+↓|4c|4α+↓|4D|4α_↓|42|¬Y), S|βi|4α=↓|4M|βi|β0|4|
4690 "b|4M|βi|β1.|'{A3}|π|≡2|≡1|≡.|9|4|πFor example,
4693 let |εu|4α=↓|42|g8|gq|gα+↓|g5,|4x|4α=↓|4(2|g(|gq|gα+↓|g1|g)|
4694 gu|4α_↓|41)/(2|gu|4α_↓|41)|4α=↓|42|gq|gu|4α+↓|4αo↓|4αo↓|4αo↓
4694 |4α+↓|42|gu|4α+↓|41, y|4α=↓|42|g(|gq|gα+↓|g1|g)|gu|4α+↓|41.
4696 |πThen |εxy|4α=↓|4(2|g2|g(|gq|gα+↓|g1|g)|gu|4α_↓|41)/(2|gu|4
4697 α_↓|41); |πif |εn|4α=↓|42|g4|g(|gq|gα+↓|g1|g)|gu|4α+↓|4xy,
4700 |πwe have |λ3|ε(n)|4|¬E|44(q|4α+↓|41)u|4α+↓|4q|4α+↓|42
4703 |πby Theorem F, but |ε|λ3|¬⊂(n)|4α=↓|44(q|4α+↓|41)u|4α+↓|42q
4707 |4α+↓|42 |πby Theorem H.|'{A3}|≡2|≡2|≡.|9|4Underline
4712 everything except the |εu|4α_↓|41 |πinsertions
4717 used in the calculation of |εx.|'{A3}|π|≡2|≡3|≡.|9|4Theorem
4724 G (everything underlined).|'{A3}|≡2|≡4|≡.|9|4Use
4728 the numbers (|εB|ga|ri|4α_↓|41)/(B|4α_↓|41),
4731 0|4|¬E|4i|4|¬E|4r, |πunderlined when |εa|βi |πis
4736 underlined; and |εc|βkB|gi|gα_↓|g1(B|gb|rj|4α_↓|41)/(B|4α_↓|
4738 41) |πfor |ε0|4|¬E|4j|4|¬W|4t, 0|4|¬W|4i|4|¬E|4k|4|¬E|4|λ3|g
4741 0(B), |πunderlined when |εc|βk |πis underlined,
4747 where |εc|β0,|4c|β1,|4.|4.|4. |πis a minimum
4752 length |λ3|g0-chain for |εB. |πTo prove the second
4760 inequality, let |εB|4α=↓|42|gm |πand use (3).
4766 (The second inequapty, is rarely, if ever, an
4774 improvement on Theorem G.)|'|Hu*?*?*?*?{U0}{H9L11M29}|πW58320#Co
folio 824 galley 6
4778 mputer|4Programming!(Knuth/Addison-Wesley)!Answers!f.|4824!g
4778 .|46d|'{A6}|≡2|≡5|≡.|9|4We may assume that |εd|βk|4α=↓|41.
4784 |πUse the rule |εR|4A|βk|βα_↓|β1|4.|4.|4.|4A|β1,
4788 |πwhere |εA|βj|4α=↓|4``XR'' |πif |εd|βj|4α=↓|41,
4792 A|βj|4α=↓|4|π``R'' otherwise, and where ``R''
4797 means take the square root, ``X'' means multiply
4805 by |εx. |πFor example, if |εy|4α=↓|4(.1101101)|β2,
4811 |πthe rule is R R XR XR R XR XR. (There exist
4823 binary square-root extraction algorithms suitable
4828 for computer hardware, requiring an execution
4834 time comparable to that of division; computers
4841 with such hardware could also calculate more
4848 general fractional powers with the technique
4854 in this exercise.)|'{A3}|≡2|≡6|≡.|9|4If we know
4860 the pair (|εF|βk,|4F|βk|βα_↓|β1), |πthen (|εF|βk|βα+↓|β1,|4F
4864 |βk)|4α=↓|4(|εF|βk|4α+↓|4F|βk|βα_↓|β1,|4F|βk)
4865 |πand (|εF|β2|βk,|4F|β2|βk|βα_↓|β1)|4α=↓|4(F|ur2|)k|)|4α+↓|4
4866 2F|βkF|βk|βα_↓|β1, F|ur2|)k|)|4α+↓|4F|ur2|)kα_↓1|));
4868 |πso a binary method can be used to calculate
4877 (|εF|βn,|4F|βn|βα_↓|β1), |πusing |εO(|πlog|4|εn)
4880 |πarithmetic operations. Perhaps better is to
4886 use the pair of values (|εF|βk,|4L|βk), |πwhere
4893 |εL|βk|4α=↓|4F|βk|βα_↓|β1|4α+↓|4F|βk|βα+↓|β1
4894 (|πcf. Section 4.5.4); then (|εF|βk|βα+↓|β1,|4L|βk|βα+↓|β1)|
4898 4α=↓|4{H11}({H9}|f1|d32|)(F|βk|4α+↓|4L|βk), |f1|d32|)(5F|βk|
4899 4α+↓|4L|βk){H11}){H9}, (F|β2|βk,|4L|β2|βk)|4α=↓|4(F|βkL|βk,
4901 L|ur2|)k|)|4α_↓|42(|→α_↓1)|gk{H11}){H9}.|'!!|1|1|πFor
4903 the general linear recurrence |εx|βn|4α=↓|4a|β1x|βn|βα_↓|β1|
4907 4α+↓|4αo↓|4αo↓|4αo↓|4α+↓|4a|βdx|βn|βα_↓|βd, |πwe
4909 can compute |εx|βn |πin |εO(d|g3|4|πlog|4|εn)
4914 |πarithmetic operations by computing the |εn|πth
4920 power of an appropriate |εd|4d |πmatrix. (This
4927 observation is due to J. C. P. Miller and D.
4937 J. S. Brown, |εComp. J. |π|≡9 (1966), 188<190.)|'
4945 {A3}|≡2|≡7|≡.|9|4First form the |ε2|gm|4α_↓|4m|4α_↓|41
4949 |πproducts |εx|ure|β1|)1|)|4.|4.|4.|4x|ure|βm|)m|),
4951 |πwhere |ε0|4|¬E|4e|βj|4|¬E|41 |πand |εe|β1|4α+↓|4αo↓|4αo↓|4
4954 αo↓|4α+↓|4e|βm|4|¬R|42. |πThen if |εn|βj|4α=↓|4(d|βj|β|≤l|4.
4957 |4.|4.|4d|βj|β1d|βj|β0)|β2, |πthe sequence begins
4961 with |εx|urd|β1|≤l|)1|)|4.|4.|4.|4x|urd|βm|β|≤l|)m|)
4963 |πand then we square, and multiply by |εx|urd|β1|βi|)1|)|4.|
4970 4.|4.|4x|urd|βm|βi|)m|), |πfor |εi|4α=↓|4|≤l|4α_↓|41,|4.|4.|
4972 4.|4,|41,|40. {H11}({H9}|πStraus [|εAMM |≡7|≡1
4976 (1964), 807<808] |πhas shown that |ε2|≤l(n) |πmay
4983 be replaced by (1|4α+↓|4|ε|≤e)|≤l(n) |πfor any
4989 |ε|≤e|4|¬Q|40, |πby generalizing this binary
4994 method to |ε2|gk-|πary as in Theorem D. At least
5003 |λ3|ε(n|β1|4α+↓|4αo↓|4αo↓|4αo↓|4α+↓|4n|βm) |πmultiplications
5004 are obviously required.{H11}){H9}|'{U0}{H9L11M29}|≡2|≡8|≡.|
5008 9|4(a) |εx|4|4|4y|4α=↓|4x|4|↔I|4y|4|↔I|4(x|4α+↓|4y),
5010 |πwhere ``|→|↔I'' is logical ``or'', cf. exercise
5017 4.6.2<26; clearly |ε|≤n(x|4|4|4y)|4|¬E|4|≤n(x|4|↔I|4y)|4α+↓|
5019 4|≤n(x|4|↔i|4y)|4α=↓|4|≤n(x)|4α+↓|4|≤n(y). |π(b)
5021 Note _rst that |εA|βi|βα_↓|β1/2|gd|ri|rα_↓|r1|4|↔Y|4A|βi/d|g
5024 i |πfor |ε1|4|¬E|4r. |πSecondly, note that |εd|βj|4α=↓|4d|βi
5030 |βα_↓|β1 |πin a nondoubling; for otherwise |εa|βi|βα_↓|β1|4|
5036 ¬R|42a|4|¬R|4a|βj|4α+↓|4a|βk|4α=↓|4a|βi. |πHence
5038 |εA|βj|4|↔Y|4A|βi|βα_↓|β1 |πand |εA|βk|4|↔Y|4A|βi|βα_↓|β1/2|
5040 gd|rj|gα_↓|gd|rk. (|πc) An easy induction on
5046 |εi, |πexcept that close steps need closer attention.
5054 Let us say that |εm |πhas property |εP(|≤a) |πif
5063 the 1's in its binary representation all appear
5071 in consecutive blocks of |ε|→|¬R|≤a |πin a row.
5079 If |εm |πand |εm|¬S |πhave |εP(|≤a), |πso does
5087 |εm|4|4|4m|¬S; |πif |εm |πhas |εP(|≤a) |πthen
5093 |ε|≤r(m) |πhas |εP(|≤a|4α+↓|4|≤d). |πHence |εB|βi
5098 |πhas |εP(1|4α+↓|4|≤dc|βi). |πFinally if |εm
5103 |πhas |εP(|≤a) |πthen |ε|≤n{H11}({H9}|≤r(m))|4|¬E|4(|≤a|4α+↓
5106 |4|≤d)|≤n(m)/|≤a; |πfor |ε|≤n(m)|4α=↓|4|≤n|β1|4α+↓|4αo↓|4αo↓
5108 |4αo↓|4α+↓|4|≤n|βq, |πwhere each block size |ε|≤n|βj
5114 |πis |ε|→|¬R|≤a, |πhence |ε|≤n{H11}({H9}|≤r(m){H11}){H9}|4|¬
5117 E|4(|≤n|β1|4α+↓|4|≤d)|4α+↓|4αo↓|4αo↓|4αo↓|4α+↓|4(|≤n|βq|4α+↓
5117 |48)|4|¬E|4(1|4α+↓|4|≤d/|≤a)|≤n|β1|4α+↓|4αo↓|4αo↓|4αo↓|4α+↓|
5117 4(1|4α+↓|4|≤d/|≤a)|≤n|βq. |π(d) Let |εf|4α=↓|4b|βr|4α+↓|4c|β
5120 r |πbe the number of nondoublings and |εs |πthe
5129 number of small steps. If |εf|4|¬R|43.271|4|πlg|4|ε|≤n(n)
5135 |πwe have |εs|4|¬R|4|πlg|4|ε|≤n(n) |πas desired,
5140 by (16). Otherwise we have |εa|βi|4|¬E|4(1|4α+↓|42|gα_↓|g|≤d
5145 )|gb|ri2|gc|ri|gα+↓|gd|ri |πfor |ε0|4|¬E|4i|4|¬E|4r,
5148 |πhence |εn|4|¬E|4{H11}({H9}(1|4α+↓|42|gα_↓|g|≤d)/2{H11}){H9
5149 }|gb|rr2|gr, |πand |εr|4|¬R|4|πlg|4|εn|4α+↓|4b|βr|4α_↓|4b|βr
5151 |4|πlg(1|4α+↓|42|ε|gα_↓|g|≤d)|4|¬R|4|πlg|4|εn|4α+↓|4|πlg|4|ε
5151 |≤n(n)|4α_↓|4|πlg(|ε1|4α+↓|4|≤dc|βr)|4α_↓|4b|βr|4|πlg(1|4α+↓
5151 |42|ε|gα_↓|g|≤d). |πLet |ε|≤d|4α=↓|4|"p|πlg(|εf|4α+↓|41)|"P;
5153 |πthen ln(|ε1|4α+↓|42|gα_↓|g|≤d)|4|¬E|4|πln{H11}({H9}1|4α+↓
5155 |41/(|εf|4α+↓|41){H11}){H9}|4|¬E|41/(f|4α+↓|41)|4|¬E|4|≤d/(1
5155 |4α+↓|4|≤df), |πand it follows that lg(1|4α+↓|4|ε|≤dx)|4α+↓|
5160 4(f|4α_↓|4x)|πlg(1|4α+↓|4|ε2|gα_↓|g|≤d)|4|¬E|4|πlg(|ε1|4α+↓|
5160 4|≤df) |πfor |ε0|4|¬E|4x|4|¬E|4f. |πHence _nally
5165 |ε|λ3(n)|4|¬R|4|πlg|4|εn|4α+↓|4|πlg|4|ε|≤n(n)|4α_↓|4|πlg{H11
5165 }({H9}1|4α+↓|4(3.271|4lg|4|ε|≤n(n){H11}){H9}|"p|πlg{H11}({H9
5165 }|ε1|4α+↓|43.271|4|πlg|4|ε|≤n(n){H11}){H11})|"P){H9}.
5166 |ε[Theoretical Computer Science |π|≡1 (1975),
5171 1<12.]|'|H|≡2|≡9|≡.|9|4In the paper just cited,
5177 Sch|=4onhage has re_ned the method of exercise
5184 28 to prove that |ε|λ3(n)|4|¬R|4|πlg|4|εn|4α+↓|4|πlg|4|ε|≤n(
5188 n)|4α_↓|42.13 |πfor all |εn. |πCan the remaining
5195 gap be closed?|'{A3}{H9}|≡3|≡0|≡.|9|4|εn|4α=↓|431
5199 |πis the smallest example; |ε|λ3(31)|4α=↓|47,
5204 |πbut 1, 2, 4, 8, 16, 32, 31 |πis an addition-subtraction
5215 chain of length 6. Erd|=4os has stated that Theorem
5224 E holds also for addition-subtraction chains.
5230 Sch|=4onhage has extended his lower bound of
5237 exercise 28 to addition-subtraction chains, with
5243 |ε|≤n(n) |πreplaced by |ε|=3|≤n(n)|4α=↓|4|πminimum
5247 number of nonzero digits to represent |εn|4α=↓|4(n|βq|4.|4.|
5253 4.|4n|β0)|β2 |πwhere each |εn|βj |πis |→α_↓1,
5259 0, or |→α+↓1; |ε|=3|≤n(n) |πis the number of
5267 1's, in the ordinary binary representation of
5274 |εn, |πwhich are immediately preceded by 0 |πor
5282 by the string 00(10)|ε|gk1 |πfor some |εk|4|¬R|40.)|'
5289 {A3}|π|≡3|≡2|≡.|9|4Andrew C. Yao has essentially
5294 found the asymptotic behavior for _xed |εm, |πby
5302 generalizing the 2|ε|gk-|πary method to obtain
5308 the upper bound |ε|≤l(n|βm)|4α+↓|4O{H11}({H9}|¬K|ur|)1|¬Ei|¬
5311 Em|)|4|≤l(n|βi)/|≤l|≤l(n|βi){H11}){H9}.|'{A24}{H10}|π|∨S|∨E|
5312 ∨C|∨T|∨I|∨O|∨N |∨4|∨.|∨6|∨.|∨4|'{A12}{H9}|9|1|≡1|≡.|9|4Set
5315 |εy|4|¬L|4x|g2, |πthen compute {H11}({H9}(αo↓|4αo↓|4αo↓|4(|ε
5318 u|β2|βn|βα+↓|β1y|4α+↓|4u|β2|βn|βα_↓|β1)y|4α+↓|4u|β1{H11}){H9
5318 }x.|'{A3}|9|1|≡2|≡.|9|4|πReplacing |εx |πin (2)
5323 |πby the polynomial |εx|4α+↓|4x|β0 |πleads to
5329 the following procedure:|'{A3}{I3.1H}!!|1|1|≡G|≡1|≡.|9Do
5333 step G2, for |εk|4α=↓|4n, n|4α_↓|41,|4.|4.|4.|4,|40
5338 (|πin this order), and stop.|'{A3}!!|1|1|≡G|≡2|≡.|9Set
5344 |εv|βk|4|¬L|4u|βk, |πand then set |εv|βj|4|¬L|4v|βj|4α+↓|4x|
5348 β0v|βj|βα+↓|β1 |πfor |εj|4α=↓|4k, k|4α+↓|41,|4.|4.|4.|4,
5352 n|4α_↓|41. (|πWhen |εk|4α=↓|4n, |πthis step simply
5358 sets |εv|βn|4|¬L|4u|βn.)|'{A3}{IC}|πThe computations
5362 turn out to be identical to those in H1, H2,
5372 but performed in a di=erent order.|'{A3}|9|1|≡3|≡.|9|4The
5379 coe∃cient of |εx|gk |πis a polynomial in |εy
5387 |πwhich may be evaluated by Horner's rule: {H11}({H9}αo↓|4αo
5394 ↓|4αo↓|4(|εu|βn|β,|β0x|4α+↓|4(u|βn|βα_↓|β1|β,|β1y|4α+↓|4u|βn
5394 |βα_↓|β1|β,|β0))x|4α+↓|4αo↓|4αo↓|4αo↓{H11}){H9}x|4α+↓|4{H11}
5394 ({H9}(αo↓|4αo↓|4αo↓|4(u|β0|β,|βny|4α+↓|4u|β0|β,|βn|βα_↓|β1)y
5394 |4α+↓|4αo↓|4αo↓|4αo↓)y|4α+↓|4u|β0|β,|β0{H11}){H9}.
5395 (|πFor a ``homogeneous'' polynomial, such as
5401 |εu|βnx|gn|4α+↓|4u|βn|βα_↓|β1x|gn|gα_↓|g1y|4α+↓|4αo↓|4αo↓|4α
5401 o↓|4α+↓|4u|β1xy|gn|gα_↓|g1|4α+↓|4u|β0y|gn, |πanother
5403 scheme is more e∃cient: _rst divide |εx |πby
5411 |εy, |πevaluate a polynomial in |εx/y, |πthen
5418 multiply by |εy|gn.{H11}){H9}|'{A3}|9|1|≡4|≡.|9|4|πRule
5422 (2) involves |ε4n |πor |ε3n |πreal multiplications
5429 and |ε4n |πor |ε7n |πreal additions; (3) is worse,
5438 it takes 4|εn|4α+↓|42 |πor |ε4n|4α+↓|41 |πmults,
5444 |ε4n|4α+↓|42 |πor |ε4n|4α+↓|45 |πodds.|'|π|9|1|≡5|≡.|9|1One
5449 multiplication to compute |εx|g2; |"ln/2|"L |πmultiplication
5454 s and |"l|εn/2|"L |πadditions to evaluate the
5461 _rst line; |"p|εn/2|"P |πmultiplications and
5466 |ε|"pn/2|"P|4α_↓|41 |πadditions to evaluate the
5471 second line; and one addition to add the two
5480 lines together. Total: |εn|4α+↓|41 |πmultiplications
5485 and |εn |πadditions.|'{A3}|9|1|≡6|≡.|9|4|≡J|≡1|≡.|9Compute
5489 and store the values |εx|ur2|)0|),|4.|4.|4.|4,|4x|urjα_↓|"ln
5493 /2|"L|)0|).|π|'{A3}!!|1|1|π|≡J|≡2|≡.|9|4Set |εv|βj|4|¬L|4u|β
5495 jx|urjα_↓|"ln/2|"L|)0|) |πfor |ε0|4|¬E|4j|4|¬E|4n.|'
5498 {A3}!!|1|1|π|≡J|≡3|≡.|9For |εk|4α=↓|40,|41,|4.|4.|4.|4,|4n|4
5499 α_↓|41, |πset |εv|βj|4|¬L|4v|βj|4α+↓|4v|βj|βα+↓|β1
5502 |πfor |εj|4α=↓|4n|4α_↓|41,|4.|4.|4.|4,|4k|4α+↓|41,|4k.|'
5504 {A3}!!|1|1|π|≡J|≡4|≡.|9Set |εv|βj|4|¬L|4v|βjx|ur|"ln/2|"Lα_↓
5505 j|)0|) |πfor |ε0|4|¬E|4j|4|¬E|4n.|'{A3}|πThere
5509 are (|εn|4α+↓|4n|g2)/2 |πadditions, |εn|4α+↓|4|"pn/2|"P|4α_↓
5512 |41 |πmultiplications, |εn |πdivisions. Another
5517 multiplication and division can be saved by treating
5525 |εv|βn |πand |εv|β0 |πas special cases. |εReference|*/:|\
5532 SIGACT News |≡7|≡, |π3 (Summer 1975), 32<34.|'
5539 {A3}|9|1|≡7|≡.|9|1|3Let |εx|βj|4α=↓|4x|β0|4α+↓|4jh,
5541 |πand consider (42), (44). Set |εy|βj|4|¬L|4u(x|βj)
5547 |πfor |ε0|4|¬E|4j|4|¬E|4n. |πFor |εk|4α=↓|41,
5551 2,|4.|4.|4.|4,|4n |π(in this order), set |εy|βj|4|¬L|4y|βj|4
5556 α_↓|4y|βj|βα_↓|β1 |πfor |εj|4α=↓|4k,|4k|4α+↓|41,|4.|4.|4.|4,
5558 |4n (|πin this order). Now |ε|≤b|βj|4α=↓|4y|βj
5564 |πfor all |εj.|'{A3}|9|1|π|≡8|≡.|9|4See (43).|'
5569 {A3}|9|1|≡9|≡.|9|4[|εCombinatorial Mathematics
5571 (|πBu=alo: Math. Ass'n of America, 1963), 26<28.]
5578 This formula can be regarded as an application
5586 of the principle of inclusion and exclusion (Section
5594 1.3.3), since the sum of the terms for |εn|4α_↓|4|≤e|β1|4α_↓
5602 |4αo↓|4αo↓|4αo↓|4α_↓|4|≤e|βn|4α=↓|4k |πis the
5605 sum of all |εx|β1|βj|m1x|β2|βj|m2|4αo↓|4αo↓|4αo↓|4x|βn|βj|mn
5608 |πfor which |εk |πvalues of the |εj, |πdo not
5618 appea. A direct proof can be given by observing
5627 that the coe∃cient of |εx|β1|βj|m1|4.|4.|4.|4x|βn|βj|mn
5632 |πis|'{A9}|ε|¬K|4(|→α_↓1)|gn|gα_↓|g|≤e|r1|gα_↓|1|gαo↓|1|gαo↓
5633 |1|gαo↓|1|gα_↓|g|≤e|rn|≤e|βj|m1|4.|4.|4.|4|≤e|βj|mn;|;
5634 {A9}|πif the |εj|π's are distinct, this equals
5641 unity, but if |εj|β1,|4.|4.|4.|4,|4j|βn|4|=|↔6α=↓|4k
5645 |πthen it is zero, since the terms for |ε|≤e|βk|4α=↓|40
5654 |πcancel the terms for |ε|≤e|βk|4α=↓|41.|'!!|1|1|πTo
5660 evaluate the sum e∃ciently, we can start with
5668 |ε|≤e|β1|4α=↓|41, |≤e|β2|4α=↓|4αo↓|4αo↓|4αo↓|4α=↓|4|≤e|βn|4α
5669 =↓|40, |πand we can then proceed through all
5677 combinations of the |ε|≤w|π's in such a way that
5686 only one |ε|≤e |πchanges from one term to the
5695 ne t. (See ``Gray code'' in Chapter 7.) The work
5705 to compute the _rst term is |εn|4α_↓|41 |πmultiplications;
5713 the subsequent 2|g|εn|4α_↓|42 |πterms each involve
5719 |εn |πadditions, then |εn|4α_↓|41 |πmultiplications,
5724 then one more addition. Total: (|ε2|gn|4α_↓|41)(n|4α_↓|41)
5730 |πmultiplications, and (|ε2|gn|4α_↓|42)(n|4α+↓|41)
5733 |πadditions. Only |εn|4α+↓|41 |πtemp storage
5738 locations are needed, one for the main partial
5746 sum and one for each factor of the cur{U0}{H9L11M29}|πW58320
folio 828 galley 7
5754 #Computer|4Programming!(Knuth/Addison-Wesley)!Answers!f.|482
5754 8!g.|47d|'{A6}|ε|≡1|≡0|≡.|9|4|ε|¬K|β1|β|¬E|βk|β|¬W|βn|4(k|4α
5755 +↓|41)(|fn|d5kα+↓1|))|4α=↓|4n(2|gn|gα_↓|g1|4α_↓|41)
5756 |πmultiplications and |ε|¬K|β1|β|¬E|βk|β|¬W|βn|4k(|fn|d5kα+↓
5758 1|))|4α=↓>n2|gn|gα_↓|g1|4α_↓|42|gn|4α+↓|41 |πadditions.
5761 This is approximately half as many arithmetic
5768 operations as the method of exercise 9, although
5776 it requires a more complicated program to control
5784 the sequence. Approximately (|ε|fn|d5|"pn/2|"P|))|4α+↓|4(|fn
5787 |d5|"pn/2|"Pα_↓1|)) |πtemporary storage locations
5791 must be used, and this grows exponentially large
5799 (on the order of 2|ε|gn/|¬H|v4n|)4|gn/n|g1|g.|g5.|'
5804 !!|1|1|πThe method in this exercise is equivalent
5811 to the unusual matrix factorization of the permanent
5819 function, given by Jurkat and Ryser in |εJ. Algebra
5828 |≡5 (|π1967), 342<357. It may also be regarded
5836 as an application of (39), (40), in an appropriate
5845 sense.|'{A3}|≡1|≡2|≡.|9|4(J. Hopcroft and L.
5850 R. Kerr have shown among other things that 7
5859 multiplications are necessary in 2|4α⊗↓|42 matrix
5865 multiplication [|εSIAM J. Appl. Math. |π|≡2|≡0
5871 (1971), 30<36]. R. L. Probert has shown that
5879 all 7-multiplication schemes, in which each multiplication
5886 takes a linear combination of elements from one
5894 matrix and multiplies by a linear combination
5901 of elements from the other, must have at least
5910 15 additions [|εSIAM J. Computing, |πto appear].
5917 The best lower bound now known for large |εn
5926 |πis |ε2n|g2|4α_↓|4n |πmultiplications, a result
5931 due to D. Kirkpatrick. For |εn|4α=↓|43, |πJ.
5938 D. Laderman [|εBull. Amer. Math. Soc. |π|≡8|≡2
5945 (1976), 126<128] has shown that 23 noncommutative
5952 multiplications su∃ce.)|'{A3}|≡1|≡3|≡.|9|4|εF(t|β1,|4.|4.|4.
5954 |4,|4t|βn)|4α=↓|4{H11}({H9}|¬K|ur|)0|¬Es|β1|¬Wm|β1,|1.|1.|1.
5954 |1,|10|¬Es|βn|¬Wm|βn|)|4|πexp{H11}({H9}|ε|→α_↓2|≤pi(s|β1t|β1
5954 /m|β1|4α+↓|4αo↓|4αo↓|4αo↓|4α+↓|4s|βnt|βn/m|βn)f(s|β1,|4.|4.|
5954 4.|4,|4s|βn){H11}){H9}/m|β1,|4.|4.|4.|4m|βn,
5955 |πby summing geometric series. The inverse transform
5962 times |εm|β1|4.|4.|4.|4m|βn |πcan be found by
5968 doing a regular transform and interchanging |εt|βj
5975 |πwith |εm|βj|4α_↓|4t|βj |πwhen |εt|βj|4|=|↔6α=↓|40,
5979 |πcf. exercise 4.3.3<15.|'!!|1|1{H11}(If we regard
5985 |εF(t|β1,|4.|4.|4.|4,|4t|βn) |πas the coe∃cient
5989 of |εx|urt|β1|)1|)|4.|4.|4.|4x|urt|βn|)n|) |πin
5992 a multivariate polynomial, the _nite Fourier
5998 transform amounts to evaluation of this polynomial
6005 at roots of unity, and the inverse transform
6013 amounts to _nding the interpolating polynomial.{H11})|'
6019 {A3}|≡1|≡4|≡.|9|4(a) Let |εm|4α=↓|42, F(t|β1,|4t|β2,|4.|4.|4
6022 .|4,|4t|βn)|4α=↓|4F(2|gn|gα_↓|g1t|βn|4α+↓|4αo↓|4αo↓|4αo↓|4α+
6022 ↓|42t|β2|4α+↓|4t|β1), f(s|β1,|4s|β2,|4.|4.|4.|4,|4s|βn)|4α=↓
6023 |4f(2|gn|gα_↓|g1s|β1|4α+↓|42|gn|gα_↓|g2s|β2|4α+↓|4αo↓|4αo↓|4
6023 αo↓|4α+↓|4s|βn); |πnote the reversed treatment
6028 between |εt|π's and |εs|π's. Also let |εg|βk(s|βk,|4.|4.|4.|
6034 4,|4s|βn,|4t|βk) |πbe |ε|≤v |πraised to the 2|ε|gk|gα_↓|g1t|
6040 βk(s|βn|4α+↓|42s|βn|βα_↓|β1|4α+↓|4αo↓|4αo↓|4αo↓|4α+↓|42|gn|g
6040 α_↓|gks|βk) |πpower. It is possible to gain some
6048 speed by combining steps |εk |πand |εk|4α+↓|41,
6055 |πfor |εk|4α=↓|41,|43,|4.|4.|4.; |πthis expedites
6059 several of the computations of sines and cosines.
6067 [The fast Fourier transform algorithm is essentially
6074 due to C. Runge and H. K|=4onig in 1924, and
6084 it was generalized by J. W. Cooley and J. W.
6094 Tukey, |εMath. Comp. |π|≡1|≡9 (1965), 297<301.
6100 Its interesting history has been traced by J.uW.
6108 Cooley, P. A. W. Lewis, P. D. Welch, |εProc.
6117 IEEE |π|≡5|≡5 (1967), 1675<1677. Details concerning
6123 its use have been discussed by R. C. Singleton,
6132 |εC|4ACM |≡1|≡0 (1967), |π647<654; M. C. Pease,
6139 |εJ|4ACM |≡1|≡5 (1968), 252<264; |πG. D. Berglund,
6146 |εMath. Comp. |≡2|≡2 (1968), 275<279, C|4ACM
6152 |≡1|≡1 (1968), |π703<710.]|'!!|1|1(a) Let |εN
6158 |πbe the smallest power of 2 which exceeds |ε2n,
6167 |πand let |εu|βn|βα+↓|β1|4α=↓|4αo↓|4αo↓|4αo↓|4α=↓|4u|βN|βα_↓
6169 |β1|4α=↓|4v|βn|βα+↓|β1|4α=↓|4αo↓|4αo↓|4αo↓|4α=↓|4v|βN|βα_↓|β
6169 1|4α=↓|40. |πIf |εU|βs|4α=↓|4|¬K|ur|)0|¬Et|¬WN|)|4u|βt|≤v|gs
6171 |gt, V|βs|4α=↓|4|¬K|ur|)0|¬Et|¬WN|)|4v|βt|≤v|gs|gt,
6173 0|4|¬E|4s|4|¬W|4N, |≤v|4α=↓|4e|g2|g|≤p|gi|g/|gN,
6175 |πthen |ε|¬K|ur|)0|¬Es|¬WN|)|4U|βsV|βs|≤v|gα_↓|gs|gt|4α=↓|4N
6176 |4|¬K|4u|βt|m1v|βt|m2. |πThe latter sum is taken
6182 over all |εt|β1 |πand |εt|β2 |πwith |ε0|4|¬E|4t|β1,
6189 t|β2|4|¬W|4N, t|β1|4α+↓|4t|β2|4|"o|4t (|πmodulo
6192 |εN). |πThe terms vanish unless |εt|β1|4|¬E|4n,
6198 t|β2|4|¬E|4n, |πso |εt|β1|4α+↓|4t|β2|4|¬W|4N;
6201 |πthus the sum is the coe∃cient of |εz|gt |πin
6210 the product |εu(z)v(z). |πIf we use the method
6218 of (a) to compute the Fourier transforms and
6226 the inverse transforms, the number of complex
6233 operations is |εO(N|4|πlog|4|εN)|4α+↓|4O(N|4|πlog|4|εN)|4α+↓
6235 |4O(N)|4α+↓|4O(N|4|πlog|4|εN); |πand |εN|4|¬W|44n.
6238 [|πCf. Section 4.3.3 and paper by J. M. Pollard,
6247 |εMath. comp. |π|≡2|≡5 (1971), 365<374.]|'{U0}{H9L11M29}!!|1
6252 |1The number |ε|≤v |πcannot be represented exactly
6259 inside a computer, but V. Strassen has shown
6267 that it isn't necessary to have too much accuracy
6276 to deduce exact results when the coe∃cients are
6284 integers [|εComputing |π|≡7 (1971), 281<292].|'
6289 !!|1|1It is possible to use an |εinteger |πnumber
6297 |ε|≤v |πwhich is of order |ε2|gt |πmodulo a prime
6306 |εp, |πand to determine the results modulo su∃ciently
6314 many primes. Useful primes in this regard, together
6322 with their least primitive roots |εr (|πfrom
6329 which we take |ε|≤v|4α=↓|4r|g(|gp|gα_↓|g1|g)|g/|g2|it|4|πmod
6332 |4|εp |πwhen |εp|4|πmod|4|ε2|gt|4α=↓|41), |πcan
6336 be found as described in Section 4.5.4. For |εt|4α=↓|49,
6345 |πthe largest cases |→|¬w2|g3|g5 |πare |εp|4α=↓|42|g3|g5|4α_
6350 ↓|4512a|4α+↓|41, |πwhere (|εa,|4r)|4α=↓|4(28,|47),
6353 (31,|410), 34,|413), (56,|43), (58,|410), (76,|45),
6358 (80,|43), (85,|411), 91,|45), (101,|43); |πthe
6363 ten largest cases |→|¬W2|g3|g1 are |εp|4α=↓|42|g3|g1|4α_↓|45
6368 12a|4α+↓|41, |πwhere (|εa,|4r)|4α=↓|4(1,|410),
6371 (11,|43), (19,|411), (20,|43), (29,|43), (35,|43),
6376 (55,|419), (65,|46), (95,|43), (121,|410). |πFor
6381 larger |εt, |πall primes |εp |πof the form |ε2|gtq|4α+↓|41
6390 |πwhere |εq|4|¬W|432 |πis odd and 2|g2|g4|4|¬W|4|εp|4|¬W|42|
6395 g3|g6 |πare given by (|εp|4α_↓|41,|4r)|4α=↓|4(11|4αo↓|42|g2|
6399 g1,|43), (25|4αo↓|42|g2|g0,|43), (27|4αo↓|42|g2|g0,|45),
6402 (25|4αo↓|42|g2|g2,|43), (27|4αo↓|42|g2|g2,|47),
6404 (5|4αo↓|42|g2|g5,|43), (7|4αo↓|42|g2|g5,|43),
6406 (7|4αo↓|42|g2|g6,|43), (27|4αo↓|42|g2|g6,|413),
6408 (15|4αo↓|42|g2|g7,|431), (17|4αo↓|42|g2|g7,|43),
6410 (3|4αo↓|42|g3|g0,|45), (13|4αo↓|42,|4|g2|g8,|43),
6412 (29|4αo↓|42|g2|g7,|43), (23|4αo↓|42|g2|g9,|45).
6414 |πSome of the latter primes can be used with
6423 |ε|≤v|4α=↓|42|ge |πfor appropriate small |εe.|'
6428 {A3}|π|≡1|≡5|≡.|9|4(a) The hint follows by integration
6434 and induction. Let |εf|g(|gn|g)(|≤u) |πtake on
6440 all values between |εA |πand |εB |πinclusive,
6447 as |ε|≤u |πvaries from min(|εx|β0,|4.|4.|4.|4,|4x|βn)
6452 |πto max(|εx|β0,|4.|4.|4.|4,|4x|βn). |πReplacing
6455 |εf|g(|gn|g) |πby these bounds, in the stated
6462 integral, yields |εA/n*3|4|¬E|4f(x|β0,|4.|4.|4.|4,|4x|βn)|4|¬
6464 E|4B/n*3. |π(b) It su∃ces to prove this for |εj|4α=↓|4n.
6473 |πLet |εf |πbe Newton's interpolation polynomial,
6479 then |εF|g(|gn|g) |πis the constant |εn*3|4|≤a|βn.|'
6485 {A3}|π|≡1|≡6|≡.|9|4Carry out the multiplications
6489 and additions of (43) as operations on polynomials.
6497 (The special case |εx|β0|4α=↓|4x|β1|4α=↓|4αo↓|4αo↓|4αo↓|4α=↓
6500 |4x|βn |πis considered in exercise 2. We have
6508 used this method in step C8 of Algorithm 4.3.3C.)|'
6517 {A3}|≡1|≡7|≡.|9|4T. M. Vari has shown that |εn|4α_↓|41
6524 |πmultiplications are necessary, by proving that
6530 |εn |πare necessary to compute |εx|ur2|)1|)|4α+↓|4αo↓|4αo↓|4
6535 αo↓|4α+↓|4x|ur2|)n|) [|πCornell Computer Science
6539 report 120 (Jan. 1972)].|'{A3}|≡1|≡8|≡.|9|4|ε|≤a|β0|4α=↓|4|f
6543 1|d32|)(u|β3/u|β4|4α+↓|41), |≤b|4α=↓|4u|β2/u|β4|4α_↓|4|≤a|β0
6544 (|≤a|β0|4α_↓|41), |≤a|β1|4α=↓|4|≤a|β0|≤b|4α_↓|4u|β1/u|β4,
6546 |≤a|β2|4α=↓|4|≤b|4α_↓|42|≤a|β1, |≤a|β3|4α=↓|4u|β0/u|β4|4α_↓|
6547 4|≤a|β1(|≤a|β1|4α+↓|4|≤a|β2), |≤a|β4|4α=↓|4u|β4.|'
6549 {A3}|π|≡1|≡9|≡.|9|4Since |ε|≤a|β5 |πis the leading
6554 coe∃cient, we may assume without loss of generality
6562 that |εu(x) |πis monic (i.e., |εu|β5|4α=↓|41).
6568 |πThen |ε|≤a|β0 |πis a root of the cubic equation
6577 40|εz|g3|4α_↓|424u|β4z|g2|4α+↓|4(4u|ur2|)4|)|4α+↓|42u|β3)z|4
6577 α+↓|4(u|β2|4α_↓|4u|β3u|β4)|4α=↓|40; |πthis equation
6580 always has at least one real root, and it may
6590 have three. Once |ε|≤a|β0 |πis determined, we
6597 have |ε|≤a|β3|4α=↓|4u|β4|4α_↓|44|≤a|β0, |≤a|β1|4α=↓|4u|β3|4α
6599 _↓|44|≤a|β0|≤a|β3|4α_↓|46|≤a|ur2|)0|), |≤a|β2|4α=↓|4u|β1|4α_
6600 ↓|4|≤a|β0(|≤a|β0|≤a|β1|4α+↓|44|≤a|ur2|)0|)|≤a|β3|4α+↓|42|≤a|
6600 β1|≤a|β3|4α+↓|4|≤a|ur3|)0|)), |≤a|β4|4α=↓|4u|β0|4α_↓|4|≤a|β3
6601 (|≤a|ur4|)0|)|4α+↓|4|≤a|β1|≤a|ur2|)0|)|4α+↓|4|≤a|β2).|'
6602 !!|1|1|πFor the given polynomial we are to solve
6610 the cubic equation 40|εz|g3|4α_↓|4120z|g2|4α+↓|480z|4α=↓|40;
6613 |πthis leads to three solutions (|ε|≤a|β0, |≤a|β1,
6621 |≤a|β2, |≤a|β3, |≤a|β4, |≤a|β5)|4α=↓|4(0, |→α_↓10,
6626 13, 5, |→α_↓5, 1), (1, |→α_↓20, 68, 1, 11, 1),
6636 (2, |→α_↓10, 13, |→α_↓3, 27, 1).|'{A9}|≡2|≡0|≡.|9|4|∂|¬l|¬d|
6642 ¬a|4|4|4!|∂|¬x|h|≤a|β0!|2|≤a|β3|9|7!!!!!!!!!|9|n|∂|¬f|¬a|¬d!
6642 |∂|≤*/|≤a|β1|≤*/!!|9|'|L|¬f|¬a|¬d|¬d|L|≤$|≤a|β3|≤$|L|¬f|¬m|¬u|
6643 ¬l|L|¬t|¬e|¬m|¬p|¬2>|L|¬s|¬t|¬a|L|¬t|¬e|¬m|¬p|¬1|L|¬f|¬a|¬d|
6644 ¬d|L|≤$|≤a|β2|≤$>|L|¬f|¬a|¬d|¬d|L|≤$|≤a|β0|≤*/|≤a|β3|≤$|L|≤f|
6645 ≤m|≤u|≤l|L|≤t|≤e|≤m|≤p|≤1>|L|¬s|¬t|¬a|L|¬t|¬e|¬m|¬p|¬2|L|¬f|
6646 ¬a|¬d|¬d|L|≤$|≤a|β4|≤$>|L|¬f|¬m|¬u|¬l|L|¬t|¬e|¬m|¬p|¬2|L|¬f|
6647 ¬m|¬u|¬l|L|≤$|≤a|β5|≤$>|L|¬s|¬t|¬a|L|¬e|¬e|¬m|¬p|¬2|'
6649 >{A3}|π|≡2|≡1|≡.|9|4|εz|4α=↓|4(x|4α+↓|41)x|4α_↓|42,
6651 w|4α=↓|4(x|4α+↓|45)z|4α+↓|49, u(x)|4α=↓|4(w|4α+↓|4z|4α_↓|48)
6652 w|4α_↓|48; |πor |εz|4α=↓|4(x|4α+↓|49)x|4α+↓|426,
6655 w|4α=↓|4(x|4α_↓|43)z|4α+↓|473, u(x)|4α=↓|4(w|4α+↓|4z|4α_↓|42
6656 4)w|4α_↓|412.|'{A3}|≡2|≡2|≡.|9|4|≤a|β6|4α=↓|41,
6658 |≤a|β0|4α=↓|4|→α_↓1, |≤a|β1|4α=↓|41, |≤b|β1|4α=↓|4|→α_↓2,
6661 |≤b|β2|4α=↓|4|→α_↓2, |≤b|β4|4α=↓|41, |≤a|β3|4α=↓|4|→α_↓4,
6664 |≤a|β2|4α=↓|40, |≤a|β4|4α=↓|44, |≤a|β5|4α=↓|4|→α_↓2.
6667 |πWe form |εz|4α=↓|4(x|4α_↓|41)x|4α+↓|41, w|4α=↓|4z|4α+↓|4x,
6670 |πand |εu(x)|4α=↓|4{H11}({H9}(z|4α_↓|4x|4α_↓|44)w|4α+↓|44{H
6672 11}){H9}z|4α_↓|4x.|'{A3}|π|≡2|≡3|≡.|9|4a) We
6675 may use induction on |εn; |πthe result is trivial
6684 if |εn|4|¬W|42. |πIf |εf(0)|4α=↓|40, |πthen the
6690 result is true for the polynomial |εf(z)/z, |πso
6698 it holds for |εf(z). |πIf |εf(iy)|4α=↓|40 |πfor
6705 some real |εy|4|=|↔6α=↓|40, |πthen |εg(|→|¬Niy)|4α=↓|4h(|→|¬
6709 Niy)|4α=↓|40; |πsince the result is true for
6716 |εf(z)/(z|g2|4α+↓|4y|g2), |πit holds also for
6721 |εf(z). |πTherefore we may assume that |εf(z)
6728 |πhas no roots whose real part is zero. Now the
6738 net number of times the given path circles the
6747 origin is the number of roots of |εf(z) |πinside
6756 the region, which is at most 1. When |εR |πis
6766 large, the path |εf(Re|gi|gt) |πfor |ε|≤p/2|4|¬E|4t|4|¬E|43|
6771 ≤p/2 |πwill circle the origin clockwise approximately
6778 |εn/2 |πtimes; so the path |εf(it) |πfor |ε|→α_↓R|4|¬E|4t|4|
6785 ¬E|4R |πmust go counterclockwise around the origin
6792 at least |εn/2|4α_↓|41 |πtimes. For |εn |πeven,
6799 this implies that |εf(it) |πcrosses the imaginary
6806 axis at least |εn|4α_↓|42 |πtimes, and the real
6814 axis at least |εn|4α_↓|43 |πtimes; for |εn |πodd,
6822 |εf(it) |πcrosses the real axis at least |εn|4α_↓|42
6830 |πtimes and the imganary axis at least |εn|4α_↓|43
6838 |πtimes. These are roots respectively of |εg(it)|4α=↓|40,
6845 h(it)|4α=↓|40.|'!!|1|1|πb)|9If not, |εg |πor
6850 |εh |πwould have a root of the form |εa|4α+↓|4bi
6859 |πwith |εa|4|=|↔6α=↓|40 |πand |εb|4|=|↔6α=↓|40.
6863 |πBut this would imply the existence of at least
6872 three other such roots, namely |εa|4α_↓|4bi |πand
6879 |→α_↓|εa|4|¬N|4bi, |πwhile |εg(z), h(z) |πhave
6884 at most |εn |πroots.|'{A3}|H=*?*?*?{U0}{H9L11M29}|πW58320#Compu
folio 832 galley 8
6888 ter|4Programming!(Knuth/Addison-Wesley)!Answers!f.|4832!g.|4
6888 8d|'{A6}|≡2|≡4|≡.|9|4The roots of |εu |πare |→α_↓7,
6895 |→α_↓3|4|¬N|4|εi, |→α_↓2|4|¬N|4i, |→α_↓1; |πpermissible
6899 values of |εc |πare |ε2 |πand 4 (|εnot |π3, since
6909 |εc|4α=↓|43 |πmakes the sum of the roots equal
6917 to zero). Case 1, |εc|4α=↓|42: p(x)|4α=↓|4(x|4α+↓|45)(x|g2|4
6922 α+↓|42x|4α+↓|42)(x|g2|4α+↓|41)(x|4α_↓|41)|4α=↓|4x|g6|4α+↓|46
6922 x|g5|4α+↓|46x|g4|4α+↓|44x|g3|4α_↓|45x|g2|4α_↓|42x|4α_↓|410;
6923 q(x)|4α=↓|46x|g2|4α+↓|44x|4α_↓|42|4α=↓|46(x|4α+↓|41)(x|4α_↓|
6923 4|f1|d33|)). |πLet |ε|≤a|β2|4α=↓|4|→α_↓1, |≤a|β1|4α=↓|4|f1|d
6926 33|); p|β1(x)|4α=↓|4x|g4|4α+↓|46x|g3|4α+↓|45x|g2|4α_↓|42x|4α
6927 _↓|410|4α=↓|4(x|g2|4α+↓|46x|4α+↓|4|f16|d33|))(x|g2|4α_↓|4|f1
6927 |d33|))|4α_↓|4|f74|d39|); |≤a|β0|4α=↓|46, |≤b|β0|4α=↓|4|f16|
6929 d33|), |≤b|β1|4α=↓|4|→α_↓|f74|d39|). |πCase 2,
6933 |εc|4α=↓|44: |πA similar analysis gives |ε|≤a|β2|4α=↓|49,
6939 |≤a|β1|4α=↓|4|→α_↓3, |≤a|β0|4α=↓|4|→α_↓6, |≤b|β0|4α=↓|412,
6942 |≤b|β1|4α=↓|4|→α_↓26.|'{A3}|π|≡2|≡5|≡.|9|4|ε|≤b|β1|4α=↓|4|≤a
6943 |β2, |≤b|β2|4α=↓|42|≤a|β1, |≤b|β3|4α=↓|4|≤a|β7,
6946 |≤b|β4|4α=↓|4|≤a|β6, |≤b|β5|4α=↓|4|≤b|β6|4α=↓|40,
6948 |≤b|β7|4α=↓|4|≤a|β1, |≤b|β8|4α=↓|40, |≤b|β9|4α=↓|42|≤a|β1|4α
6950 _↓|4|≤a|β8.|'{A3}|π|≡2|≡6≡.|9|4(a) |ε|≤l|β1|4α=↓|4|≤a|β1|4α⊗
6952 ↓|4|≤l|β0, |≤l|β2|4α=↓|4|≤a|β2|4α+↓|4|≤l|β1,
6954 |≤l|β3|4α=↓|4|≤l|β2|4α⊗↓|4|≤l|β0, |≤l|β4|4α=↓|4|≤a|β3|4α+↓|4
6955 |≤l|β3, |≤l|β5|4α=↓|4|≤l|β4|4α⊗↓|4|≤l|β0, |≤l|β6|4α=↓|4|≤a|β
6957 4|4α+↓|4|≤l|β5. |π(b) |ε|≤k|β1|4α=↓|41|4α+↓|4|≤b|β1x,
6960 |≤k|β2|4α=↓|41|4α+↓|4|≤b|β2|≤k|β1x, |≤k|β3|4α=↓|41|4α+↓|4|≤b
6961 |β3|≤k|β2x, u(x)|4α=↓|4|≤b|β4|≤k|β3|4α=↓|4|≤b|β1|≤b|β2|≤b|β3
6962 |≤b|β4x|g3|4α+↓|4|≤b|β2|≤b|β3|≤b|β4x|g2|4α+↓|4|≤b|β3|≤b|β4x|
6962 4α+↓|4|≤b|β4. |π(c) If any coe∃cient is zero,
6969 the coe∃cient of |εx|g3 |πmust also be zero in
6978 (b), while (a) yields an arbitrary polynomial
6985 |ε|≤a|β1x|g3|4α+↓|4|≤a|β2x|g2|4α+↓|4|≤a|β3x|4α+↓|4|≤a|β4
6986 |πof degree |→|¬E3.|'{A3}|≡2|≡7|≡.|9|4Otherwise
6990 there would be a nonzero polynomial |εf(q|βn,|4.|4.|4.|4,|4q
6996 |β1,|4q|β0) |πwith integer coe∃cients such that
7002 |εqn|4αo↓|4f(q|βn,|4.|4.|4.|4,|4q|β1,|4q|β0)|4α=↓|40
7003 |πfor all sets (|εq|βn,|4.|4.|4.|4,|4q|β0) |πof
7008 real numbers. This cannot happen, since it is
7016 easy to prove by induction on |εn |πthat a nonzero
7026 polynomial always takes on some nonzero value.
7033 (However, this result is false for|ε⊂nite |π_elds
7040 in place of the real numbers.)|'{A3}|≡2|≡8|≡.|9|4The
7047 indeterminate quantities |ε|≤a|β1,|4.|4.|4.|4,|4|≤a|βs
7050 |πform an algebraic basis for |εQ[|≤a|β1,|4.|4.|4.|4,|4|≤a|β
7055 s], |πwhere |εQ |πis the _eld of rational numbers.
7064 Since |εs|4α+↓|41 |πis greater than the number
7071 of elements in a basis, the polynomials |εf|βj(|≤a|β1,|4.|4.
7078 |4.|4,|4|≤a|βs) |πare algebraically dependent;
7082 this means that that there is a nonzero polynomial
7091 |εg |πwith rational coe∃cients such that |εg{H11}({H9}f|β0(|
7097 ≤a|β1,|4.|4.|4.|4,|4|≤a|βs),|4.|4.|4.|4,|4f|βs(|≤a|β1,|4.|4.
7097 |4.|4,|4|≤a|βs){H11}){H9} |πis identically zero.|'
7101 {A3}|≡2|≡9|≡.|9|4Given |εj|β0,|4.|4.|4.|4,|4j|βt|4|¬A|4|¬T0,
7102 |41,|4.|4.|4.|4,|4n|¬Y, |πthere are nonzero polynomials
7107 with integer coe∃cients such that |εg|βj(q|βj|m0,|4.|4.|4.|4
7112 ,|4q|βj|mt)|4α=↓|40 |πfor all (|εq|βn,|4.|4.|4.|4,|4q|β0)
7116 |πin |εR|βj, 1|4|¬E|4j|4|¬E|4m. |πThe product
7121 |εg|β1g|β2|4.|4.|4.|4g|βm |πis therefore zero
7125 for all (|εq|βn,|4.|4.|4.|4,|4q|β0) |πin |εR|β1|4|↔q|4αo↓|4α
7129 o↓|4αo↓|4|↔q|4R|βm.|'{A3}|≡3|≡0|≡.|9|4|πStarting
7131 with the construction in Theorem M, we will prove
7140 that |εm|β2|4α+↓|4(1|4α_↓|4|≤d|β0|βm|m1) |πof
7143 the |ε|≤b|π's may e=ectively be eliminated: If
7150 |ε|≤u|βi |πcorresponds to a parameter multiplication,
7156 we have |ε|≤m|βi|4α=↓|4|≤b|β2|βi|βα_↓|β1|4α⊗↓|4(T|β2|βi|4α+↓
7158 |4|≤b|β2|βi); |πadd |εc|≤b|β2|βi|βα_↓|β1|≤b|β2|βi
7161 |πto each |ε|≤b|βj |πfor which |εc|≤m|βi |πoccurs
7168 in |εT|βj, |πand replace |ε|≤b|β2|βi |πby zero.
7175 This removes one aprameter multiplication. If
7181 |ε|≤m|βi |πis the _rst chain multiplication,
7187 then |ε|≤m|βi |πis the _rst chain multiplication,
7194 then |ε|≤m|βi|4α=↓|4(|≤g|β1x|4α+↓|4|≤u|β1|4α+↓|4|≤b|β2|βi|βα
7195 _↓|β1)|4α⊗↓|4(|≤g|β2|βx|4α+↓|4|≤u|β2|4α+↓|4|≤b|β2|βi),
7196 |πwhere |ε|≤g|β1, |≤g|β2, |≤u|β1, |≤u|β2 |πare
7202 polynomials in |ε|≤b|β1,|4.|4.|4.|4,|4|≤b|β2|βi|βα_↓|β2
7205 |πwith integer coe∃cients. Here |ε|≤u|β1 |πand
7211 |ε|≤u|β2 |π can be ``absorbed'' into |ε|≤b|β2|βi|βα_↓|β1
7218 |πand |ε|≤b|β2|βi, |πrespectively, so we may
7224 assume that |ε|≤u|β1|4α=↓|4|≤u|β2|4α=↓|40. |πNow
7228 add |εc|≤b|β2|βi|βα_↓|β1|≤b|β2|βi |πto each |ε|≤b|βj
7233 |πfor which |εc|≤m|βi |πoccurs in |εT|βj; |πadd
7240 |ε|≤b|β2|βi|βα_↓|β1|≤g|β2/|≤g|β1 |πto |ε|≤b|β2|βi;
7243 |πand set |ε|≤b|β2|βi|βα_↓|β1 |πto zero. The
7249 result set is unchanged by this elimination of
7257 |ε|≤b|β2|βi|βα_↓|β1, |πexcept for the values
7262 of |ε|≤a|β1,|4.|4.|4.|4,|4|≤a|βs |πsuch that
7266 |ε|≤g|β1 |πis zero. {H11}({H9}This proof is essentially
7273 due to V. Ya. Pan, |εRussian Mathematical Surveys
7281 |π|≡2|≡1 (1966), 105<136.{H11}){H9} The latter
7286 case can be handled as in the proof of Theorem
7296 A, since the polynomials with |ε|≤g|β1|4α=↓|40
7302 |πcan be evaluated by eliminating |ε|≤b|β2|βi
7308 (|πas in the _rst construction, where |ε|≤m|βi
7315 |πcorresponds to a parameter multiplication).|'
7320 {A3}|≡3|≡1|≡.|9|4Otherwise we could add one parameter
7326 multiplication as a _nal step, and violate Theorem
7334 C. (The exercise is an improvement over Theorem
7342 A, in this special case since there are only
7351 |εn |πdegrees of freedom in the coe∃cients of
7359 a monic polynomial of degree |εn.)|'{A3}|≡3|≡2|≡.|9|4|≤l|β1|
7365 4α=↓|4|≤l|β0|4α⊗↓|4|≤l|β0, |≤l|β2|4α=↓|4|≤a|β1|4α⊗↓|4|≤l|β1,
7366 |≤l|β3|4α=↓|4|≤a|β2|4α+↓|4|≤l|β2, |≤l|β4|4α=↓|4|≤l|β3|4α⊗↓|
7368 4|≤l|β1,|4|≤l|β5|4α=↓|4|≤a|β3|4α+↓|4|≤l|β4. |πWe
7370 need at least three multiplications to compute
7377 |εu|β4x|g4 (|πsee Section 4.6.3), and at least
7384 two additions by Theorem A.|'{A3}|≡3|≡3|≡.|9|4We
7390 must have |εn|4α+↓|41|4|¬E|42m|β1|4α+↓|4m|β2|4α+↓|4|≤d|β0|βm
7392 |m1, |πand |εm|β1|4α+↓|4m|β2|4α=↓|4(n|4α+↓|41)/2;
7395 |πso there are no parameter multiplications.
7401 Now the _rst |ε|≤l|βi |πwhose leading coe∃cient
7408 (as a polynomial in |εx) |πis not an integer
7417 must be obtained by a chain addition; and there
7426 must be at least |εn|4α+↓|41 |πparameters, so
7433 there are at least |εn|4α+↓|41 |πparameter additions.|'
7440 {A3}|≡3|≡4|≡.|9|4Transform the given chain step
7445 by step, and also de_ne the ``content'' |εc|βi
7453 |πof |ε|≤l|βi, |πas follows: (Intuitively, |εc|βi
7459 |πis the leading coe∃cient of |ε|≤l|βi.) |πDe_ne
7466 |εc|β0|4α=↓|41. |π(a) If the step has the form
7474 |ε|≤l|βi|4α=↓|4|≤a|βj|4α+↓|4|≤l|βk, |πreplace
7476 it by |ε|≤l|βi|4α=↓|4|≤b|βj|4α=↓|4|≤a|βj/c|βk;
7479 |πand de_ne |εc|βi|4α=↓|4c|βk. |π(b) |πIf the
7485 step has the form |ε|≤l|βi|4α=↓|4|≤a|βj|4α_↓|4|≤l|βk,
7490 |πreplace it by |ε|≤l|βi|4α=↓|4|≤b|βj|4α+↓|4|≤l|βk,
7494 |πwhere |ε|≤b|βj|4α=↓|4|≤a|βj/c|βk; |πand de_ne|εc|βi|4α=↓|4
7497 c|βk. (|πb) If the step has the form |ε|≤l|βi|4α=↓|4|≤a|βj|4
7505 α_↓|4|≤l|βk, |πreplace it by |ε|≤l|βi|4α=↓|4|≤b|βj|4α+↓|4|≤l
7509 |βk, |πwhere |ε|≤b|βj|4α=↓|4|→α_↓|≤a|βj/c|βk;
7512 |πand de_ne |εc|βi|4α=↓|4|→α_↓c|βk. (|πc) If
7517 the step has the form |ε|≤l|βi|4α=↓|4|≤a|βj|4α⊗↓|4|≤l|βk,
7523 |πreplace it by |ε|≤l|βi|4α=↓|4|≤l|βk (|πthe
7528 step will be deleted later); and de_ne |εc|βi|4α=↓|4|≤a|βjc|
7535 βk. |π(d) If the step has the form |ε|≤l|βi|4α=↓|4|≤l|βj|4α⊗
7543 ↓|4|≤l|βk, |πleave it unchanged; and de_ne |εc|βi|4α=↓|4c|βj
7549 c|βk.|'!!|1|1|πAfter this process is _nished,
7555 delete all steps of the form |ε|≤l|βi|4α=↓|4|≤l|βk,
7562 |πreplacing |ε|≤l|βi |πby |ε|≤l|βk |πin each
7568 future step which uses |ε|≤l|βj. |πThen add a
7576 _nal step |ε|≤l|βr|βα+↓|β1|4α=↓|4|≤b|4α⊗↓|4|≤l|βr,
7579 |πwhere |ε|≤b|4α=↓|4c|βr. |πThis is the desired
7585 scheme, since it is easy to verify that the new
7595 |ε|≤l|βi |πare just the old ones divided by the
7604 factor |εc|βi. |πThe |ε|≤b|π's are given functions
7611 of the |ε|≤a|π's; division by zero is no problem,
7620 because if any |εc|βk|4α=↓|40 |πwe must have
7627 |εc|βr|4α=↓|40 (|πhence the coe∃cient of |εx|gn
7633 |πis zero), or else |ε|≤l|βk |πnever contributes
7640 to the _nal result.|'{A3}|≡3|≡5|≡.|9|4Since there
7646 are at least _ve parameter steps, the result
7654 is trivial unless there is at least one parameter
7663 multiplication; considering the ways in which
7669 three multiplications can form |εu|β4x|g4, |πwe
7675 see that there must be one parameter multiplication
7683 and two chain multiplications. Therefore the
7689 four addition-subtractions must each be parameter
7695 steps, and exercise 34 applies. We can now assume
7704 that only additions are used, and that we have
7713 a chain to compute a general |εmonic |πfourth
7721 degree polynomial with |εtwo |πchain multiplications
7727 and four parameter additions. The only possible
7734 scheme of this type which calculates a fourth
7742 degree polynomial has the form|'{A9}|ε|≤l|β1|4α=↓|4|≤a|β1|4α
7747 +↓|4|≤l|β0|;{A4}|≤l|β2|4α=↓|4|≤a|β2|4α+↓|4|≤l|β0|;
7749 {A4}|≤l|β3|4α=↓|4|≤l|β1|4α⊗↓|4|≤l|β2|;{A4}|≤l|β4|4α=↓|4|≤a|β
7750 3|4α+↓|4|≤l|β3|;{A4}|≤l|β5|4α=↓|4|≤a|β4|4α+↓|4|≤l|β3|;
7752 {A4}|≤l|β6|4α=↓|4|≤l|β4|4α⊗↓|4|≤l|β5|;{A4}|≤l|β7|4α=↓|4|≤a|β
7753 5|4α+↓|4|≤l|β6|;{A9}|πActually this chain has
7758 one addition too many, but any correct scheme
7766 can be put into this form if we restrict some
7776 of the |ε|≤a|π's to be the functions of the others.
7786 Now |ε|≤l|β7 |πhas the form (|εx|g2|4α+↓|4Ax|4α+↓|4B)(x|g2|4
7791 α+↓|4Ax|4α+↓|4C)|4α+↓|4D|4α=↓|4x|g4|4α+↓|42Ax|g3|4α+↓|4(E|4α
7791 +↓|4A|g2)x|g2|4α+↓|4EA|βx|4α+↓|4F, |πwhere |εA|4α=↓|4|≤a|β1|
7793 4α+↓|4|≤a|β2, B|4α=↓|4|≤a|β1|4α+↓|4|≤a|β2, B|4α=↓|4|≤a|β1|≤a
7795 |β2|4α+↓|4|≤a|β3, C|4α=↓|4|≤a|β1|≤a|β2|4α+↓|4|≤a|β4,
7797 D|4α=↓|4|≤a|β6, E|4α=↓|4B|4α+↓|4C, F|4α=↓|4BC|4α+↓|4D;
7800 |πand since this involves only three independent
7807 parameters it cannot represent a general monic
7814 fourth-degree polynomial.|'{A3}|ε|∂|≤l|β1|9|2|∂α=↓|4|≤a|β1|4
7816 α+↓|4|≤l|β0!!!!|∂|≤l|β1|9|2|∂α=↓|4|≤a|β1|4α+↓|4|≤l|β0|;
7817 {A4}|L|≤l|β2|Lα=↓|4|≤a|β2|4α+↓|4|≤l|β0|L|≤l|β2|Lα=↓|4|≤a|β2|
7817 4α+↓|4|≤l|β0>{A4}|L|≤l|β3|Lα=↓|4|↔l|β1|4α⊗↓|4|≤l|β2|L|≤l|β3|
7818 Lα=↓|4|≤l|β1|4α⊗↓|4|≤l|β2>{A4}|L|≤l|β4|Lα=↓|4|≤a|β3|4α+↓|4|≤
7819 l|β0|L|≤l|β4|Lα=↓|4|≤a|β3|4α+↓|4|≤l|β3>{A4}|L|≤l|β5|Lα=↓|4|≤
7820 a|β4|4α+↓|4|≤l|β3|L|≤l|β5|Lα=↓|4|≤a|β4|4α+↓|4|≤l|β3>
7821 {A4}|L|≤l|β6|Lα=↓|4|≤l|β4|4α⊗↓|4|≤l|β5|L|≤l|β6|Lα=↓|4|≤l|β4|
7821 4α⊗↓|4|≤l|β5>{A4}|L|≤l|β7|Lα=↓|4|≤a|β5|4α+↓|4|≤l|β6|L|≤l|β7|
7822 Lα=↓|4|≤a|β5|4α+↓|4|≤l|β3>{A4}|L|≤l|β8|Lα=↓|4|≤a|β6|4α+↓|4|≤
7823 l|β6|L|≤l|β8|Lα=↓|4|≤a|β6|4α+↓|4|≤l|β6>{A4}|L|≤l|β9|Lα=↓|4|≤
7824 l|β7|4α⊗↓|4|≤l|β8|L|≤l|β9|Lα=↓|4|≤l|β7|4α⊗↓|4|≤l|β8>
7825 {A4}|L|≤l|β1|β0|Lα=↓|4|≤a|β7|4α+↓|4|≤l|β9|L|≤l|β1|β0|Lα=↓|4|
7825 ≤a|β7|4α+↓|4|≤l|β9>{A9}|πwhere, as in exercise
7830 35, an extra addition has been inserted to cover
7839 a more general case. Neither of these schemes
7847 can calculate a general sixth-degree monic polynomial,
7854 since the _rst case is a polynomial of the form|'
7864 {A9}(|εx|g3|4α+↓|4Ax|g2|4α+↓|4Bx|4α+↓|4C)(x|g3|4α+↓|4Ax|g2|4
7864 α+↓|4Bx|4α+↓|4D)|4α+↓|4E,|;{A9}|πand in the second
7869 case (cf. exercise 35) is a polynomial of the
7878 form|'{A9}{H11}({H9}|εx|g4|4α+↓|42Ax|g3|4α+↓|4(E|4α+↓|4A|g2)
7879 x|g2|4α+↓|4EAx|4α+↓|4F{H11}){H9}(x|g2|4α+↓|4Ax|4α+↓|4G)|4α+↓
7879 |4H;|;{A9}|πboth of these involve only _ve independent
7887 parameters.|'{A3}|≡3|≡7|≡.|9|4Let |εu|g[|g0|g](x)|4α=↓|4u|βn
7889 x|gn|4α+↓|4u|βn|βα_↓|β1x|gn|gα_↓|g1|4α+↓|4αo↓|4αo↓|4αo↓|4α+↓
7889 |4u|β0, v|g[|g0|g](x)|4α=↓|4x|gn|4α+↓|4v|βn|βα_↓|β1x|gn|gα_↓
7890 |g1|4α+↓|4αo↓|4αo↓|4αo↓|4α+↓|4v|β0. |πFor |ε1|4|¬E|4j|4|¬E|4
7892 n, |πdivide |εu[|gj|gα_↓|g1|g](x) |πby the monic
7898 polynomial |εv|g[|gj|gα_↓|g1|g](x), |πobtaining
7901 |εu|g[|gj|gα_↓|g1|g](x)|4α=↓|4|≤a|βjv|g[|gj|gα_↓|g1|g](x)|4α
7901 +↓|4|≤b|βjv|g[|gj|g](x). |πAssume that a monic
7906 polynomial |εv|g[|gj|g](x) |πof degree |εn|4α_↓|4j
7911 |πexists satisfying this relation; this will
7917 be true for almost all rational functions. Let
7925 |εu|g[|gj|g](x)|4α=↓|4v|g[|gj|gα_↓|g1|g](x)|4α_↓|4xv|g[|gj|g
7925 ](x). |πThese de_nitions imply that deg(|ε|gu|g])|4|¬W|41,
7931 |πso we may let |ε|≤a|βn|βα+↓|β1|4α=↓|4u|g[|gn|g](x).|'
7936 !!|1|1|πFor the given rational function we have|'
7943 {A9}|ε|∂!|≤a|βj!|∂!|≤b|βj!|∂v|g[|gj|g](x)!|∂!|9u|g[|gj|g](x)
7943 |9!|∂|;{A3}|>1|;2|;x|4α+↓|45|;3x|4α+↓|419|;>|>
7951 3|;4|;1|;5|;>{A9}|πso |εu|g[|g0|g](x)/v|g[|g0|g](x)|4α=↓|41|
7957 4α+↓|42/{H11}({H9}x|4α+↓|43|4α+↓|44/(x|4α+↓|45){H11}){H9}.|'
7958 |ε|*/Notes:|\ |πA general rational function of
7964 the stated form has |ε2n|4α+↓|41 |π``degrees
7970 of freedom,'' in the sense that it can be shown
7980 to have |ε2n|4α+↓|41 |πessentially independent
7985 parameters. If we generalize polynomial chains
7991 to ``arithmetic chains,'' which allow division
7997 operations as well as addition, subtraction,
8003 and multiplication, we can obtain the following
8010 results with slight modi_cations to the proofs
8017 of Theorems A |πand M: |εAn arithmetic chain
8025 with q addition-subtraction steps has at most
8032 q|4α+↓|41 degrees of freedom. An arithmetic chain
8039 with m multiplication-division steps has at most
8046 2m|4α+↓|41 degrees of freedom. |πTherefore an
8052 arithmetic chain which computes almost all ration
8059 functions of the stated form must have at least
8068 |ε2n |πaddition-subtractions, and |εn |πmultiplication-divis
8072 ions; the method in this exercise is ``optimal.''|'
8080 |H=*?*?{U0}{H9L11M29}|πW58320#Computer|4Programming!(Knuth/Add
folio 835 galley 9
8080 ison-Wesley)!Answers!f.|4835!g.|49d|'{A7}|≡3|≡8|≡.|9|4The
8082 theorem is certainly ture if |εn|4α=↓|40. |πAssume
8089 that |εn |πis positive, and that a polynomial
8097 chain computing |εP(x;|4u|β0,|4.|4.|4.|4,|4u|βn)
8100 |πis given, where each of the parameters |ε|≤a|βj
8108 |πhas been replaced by a real number. Let |ε|≤l|βi|4α=↓|4|≤l
8116 |βj|4α⊗↓|4|≤l|βk |πbe the _rst chain multiplication
8122 step which involves one of |εu|β0,|4.|4.|4.|4,|4u|βn;
8128 |πsuch a step must exist because of the rank
8137 of |εA. |πWithout loss of generality, we may
8145 assume that |ε|≤l|βj |πinvolves |εu|βn; |πthus,
8151 |ε|≤l|βj |πhas the form |εh|β0u|β0|4α+↓|4αo↓|4αo↓|4αo↓|4α+↓|
8155 4h|βnu|βn|4α+↓|4f(x), |πwhere |εh|β0,|4.|4.|4.|4,|4h|βn
8158 |πare real, |εh|βn|4|=|↔6α=↓|40, |πand |εf(x)
8163 |πis a polynomial with real coe∃cients. {H11}({H9}The
8170 |εh|π's and the coe∃cients of |εf(x) |πare derived
8178 from the values assigned to the |ε|≤a|π's.{H11}){H9}|'
8185 !!|1|1Now change step |εi |πto |ε|≤l|βi|4α=↓|4|≤a|4α⊗↓|4|≤l|
8190 βk, |πwhere |ε|≤a |πis an arbitrary real number.
8198 (We could take |ε|≤a|4α=↓|40; |πgeneral |ε|≤a
8204 |πis used here merely to show that there is a
8214 certain amount of ⊗exibility available in the
8221 proof.) Add further steps to calculate|'{A9}|ε|≤l|4α=↓|4{H11
8227 }({H9}|≤a|4α_↓|4f(x)|4α_↓|4h|β0u|β0|4α_↓|4αo↓|4αo↓|4αo↓|4α_↓
8227 |4h|βn|βα_↓|β1u|βn|βα_↓|β1{H11}){H9}/h|βn;|;{A9}|πthese
8229 new steps involve only additions and parameter
8236 multiplications (by suitable new parameters).
8241 Finally, replace |ε|≤l|βα_↓|βn|βα_↓|β1|4α=↓|4u|βn
8244 |πeverywhere in the chain by this new element
8252 |ε|≤l. |πThe result is a chain which calculates|'
8260 {A9}|εQ(x;|4u|β0,|4.|4.|4.|4,|4u|βn|βα_↓|β1)|4α=↓|4P(x;|4u|β
8260 0,|4.|4.|4.|4,|4u|βn|βα_↓|β1,|4(|≤a|4α_↓|4f(x)|4α_↓|4h|β0u|β
8260 0|4α_↓|4αo↓|4αo↓|4αo↓|4α_↓|4h|βn|βα_↓|β1u|βn|βα_↓|β1)/h|βn{H
8260 11}){H9};|'{A9}|πand this chain has one less
8267 chain multiplication. The proof will be complete
8274 if we can show that |εQ |πsatis_es the hypotheses.
8283 The quantity {H11}({H9}|ε|≤a|4α_↓|4f(x){H11}){H9}/h|βn
8286 |πleads to a possibly increased value of |εm,
8294 |πand a new vector |εB|¬S. |πIf the columns of
8303 |εA |πare |εA|β0,|4A|β1,|4.|4.|4.|4,|4A|βn |π(these
8307 vectors being linearly independent over the reals),
8314 the new matrix |εA|¬S |πcorresponding to |εQ
8321 |πhas the column vectors|'{A9}|εA|β0|4α_↓|4(h|β0/h|βn)A|βn,!
8325 !.|4.|4.|4,!!A|βn|βα_↓|β1|4α_↓|4(h|βn|βα_↓|β1/h|βn)A|βn,|;
8326 {A9}|πplus perhaps a few rows of zeros to account
8335 for an increased value of |εm, |πand these columns
8344 are clearly also linearly independent. By induction,
8351 the chain which computes |εQ |πhas at least |εn|4α_↓|41
8360 |πchain multiplications, so the original chain
8366 has at least |εn.|'!!|1|1|π(This proof of Ostrowski's
8374 conjecture is taken from Garsia's unpublished
8380 notes. An independent proof, which shows further
8387 that the possibility of division gives no improvement,
8395 was published by Pan in his survey paper cited
8404 in connection with exercise 30. Generalizations
8410 to the computation of several polynomials in
8417 several variables, with and without various kinds
8424 of preconditioning, have been given by S. Winograd,
8432 |εComm. Pure and Applied Math. |π|≡2|≡3 (1970),
8439 165<179. In particular, Winograd showed that
8445 at least |εmn |πmultiplications are needed to
8452 multiply a general |εm|4α⊗↓|4n |πmatrix by the
8459 vector (|εx|β1,|4.|4.|4.|4,|4x|βn), |πand at
8463 least |"l|f1|d32|)|εmn|"L |πof these do not depend
8470 only on the entries of the matrix or only on
8480 the entries of the vector.|'{A3}|≡3|≡9|≡.|9|4By
8486 induction on |εm. |πLet |εw|βm(x)|4α=↓|4x|g2|gm|4α+↓|4u|β2|β
8490 m|βα_↓|β1x|g2|gm|gα_↓|g1|4α+↓|4αo↓|4αo↓|4αo↓|4α+↓|4u|β0,
8491 w|βm|βα_↓|β1(x)|4α=↓|4x|g2|gm|gα_↓|g2|4α+↓|4v|β2|βm|βα_↓|β3x
8491 |g2|gm|gα_↓|g3|4α+↓|4αo↓|4αo↓|4αo↓|4α+↓|4v|β0,
8492 a|4α=↓|4|≤a|β1|4α+↓|4|≤g|βm, b|4α=↓|4|≤a|βm,
8494 |πand let |εf(r)|4α=↓|4|¬K|βi|β,|βj|β|¬R|β0|4(|→α_↓1)|gi|gα+
8496 ↓|gj(|fiα+↓j|d5j|))u|βr|βα+↓|βi|βα+↓|β2|βja|gib|gj.
8497 |πIt follows that |εv|βr|4α=↓|4f(r|4α+↓|42) |πfor
8502 |εr|4|¬R|40, |πand |ε|≤d|βm|4α=↓|4f(1). |πIf
8506 |ε|≤d|βm|4α=↓|40 |πand |εa |πis given, we have
8513 a polynomial of degree |εm|4α_↓|41 |πin |εb,
8520 |πwith leading coe∃cient |→|¬N(|εu|β2|βm|βα_↓|β1|4α_↓|4ma)|4
8523 α=↓|4|→|¬N(|≤g|β2|4α+↓|4αo↓|4αo↓|4αo↓|4α+↓|4|≤g|βm|4α_↓|4m|≤
8523 g|βm).|'!!|1|1|πIn Motzkin's unpublished notes
8528 he arranged to make |ε|≤d|βk|4α=↓|40 |πalmost
8534 always, by choosing |ε|≤g|π's so that this leading
8542 coe∃cient is |=|↔6|→α=↓0 when |εm |πis even and
8550 |→α=↓0 when |εm |πis odd; then we almost always
8559 can let |εb |πbe a (real) root of an odd-degree
8569 polynomial.|'{A3}|≡4|≡0|≡.|9|4No; S. Winograd
8573 found a way to compute all polynomials of degree
8582 13 with only 7 (possibly complex) multiplications
8589 [|εComm. Pure and Applied Math. |π|≡2|≡5 (1972),
8596 455<457]. L. Revah found schemes which evaluate
8603 almost all polynomials of degree |εn|4|¬R|49
8609 |πwith |ε|"ln/2|"L|4α+↓|41 (|πpossibly complex)
8613 multiplications |ε[SIAM J. Computing |π|≡4 (1975),
8619 381<392]; for |εn|4α=↓|49 |πher scheme is |εu(x)|4α=↓|4{H11}
8625 ({H9}v(x)(x|4α+↓|4|≤a)|4α_↓|4{H11}({H9}v(x)|4α+↓|4|≤b{H11}){
8625 H9}(x|4α+↓|4|≤g)|4α+↓|4|≤d{H11}){H9}|4αo↓|4{H11}({H9}v(x)(x|
8625 4α+↓|4|≤a)|4α+↓|4|≤e{H11}){H9}|4α+↓|4|≤j, |πwhere
8627 |εv(x) |πis a monic polynomial of degree 4. By
8636 appending su∃ciently many additions (cf. exercise
8642 39), the ``almost all'' and ``possibly complex''
8649 provisos disappear.|'{A3}|≡4|≡1|≡.|9|4|εa(c|4α+↓|4d)|4α_↓|4(
8651 a|4α+↓|4b)d|4α+↓|4i{H11}({H9}a(c|4α+↓|4d)|4α+↓|4(b|4α_↓|4a)c
8651 {H11}){H9}; |πor (cf. Eq. 4.3.3 with |ε2|gn |πreplaced
8659 by |εi*3) ac|4α_↓|4bd|4α+↓|4i{H11}({H9}(a|4α+↓|4b)(c|4α+↓|4d)
8661 |4α_↓|4ac|4α_↓|4bd{H11}){H9}; |πetc. [Beware
8664 numerical instability.]|'{A3}|π|≡4|≡2|≡.|9|4a)|9Let
8667 |ε|≤p|β1,|4.|4.|4.|4,|4|≤p|βm |πbe the |ε|≤l|βi|π's
8671 which correspond to chain multiplications; then
8677 |ε|≤p|βi|4α=↓|4P|β2|βi|βα_↓|β1|4α⊗↓|4P|β2|βi
8678 |πand |εu(x)|4α=↓|4P|β2|βm|βα+↓|β1, |πwhere each
8682 |εP|βj |πhas the form |ε|≤b|βj|4α+↓|4|≤b|βj|β0x|4α+↓|4|≤b|βj
8686 |β1|≤p|β1|4α+↓|4αo↓|4αo↓|4αo↓|4α+↓|4|≤b|βj|βr|β(|βj|β)|≤p|βr
8686 |β(|βj|β), |πwhere |εr(j)|4|¬E|4|"pj/2|"P|4α_↓|41
8689 |πand each of the |ε|≤b|βj |πand |ε|≤b|βj|βk
8696 |πis a polynomial in the |ε|≤a|π's with integer
8704 coe∃cients. We can systematically modify the
8710 chain (cf. exercise 30) so that |ε|≤b|βj|4α=↓|40
8717 |πand |ε|≤b|βj|βr|β(|βj|β)|4α=↓|41, |πfor 1|4|¬E|4|εj|4|¬E|4
8720 2m; |πfurthermore we can assume that |ε|≤b|β3|β0|4α=↓|40.
8727 |πThe result set now has at most |εm|4α+↓|41|4α+↓|4|¬K|ur|)1
8734 |¬Ej|¬E2m|)|4(|"pj/2|"P|4α_↓|41)|4α=↓|4m|g2|4α+↓|41
8735 |πdegrees of freedom.|'!!|1|1b)|9Any such polynomial
8741 chain with at most |εm |πchain multiplications
8748 can be simulated by one with the form considered
8757 in (a), except that now we let |εr(j)|4α=↓|4|"pj/2|"P|4α_↓|4
8764 1 |πfor 1|4|¬E|4j|4|¬E|4|ε2m|4α+↓|41, |πand we
8769 do not assume that |ε|≤b|β3|β0|4α=↓|40 |πor that
8776 |ε|≤b|βj|βr|β(|βj|β)|4α=↓|41 |πfor |εj|4|¬R|43.
8779 |πThis single canonical form involves |εm|g2|4α+↓|42m
8785 |ε|≤b|π's. As the |ε|≤a|π's run thru all integers
8793 and as we run through all chains, the |ε|≤b|π's
8802 run through at most |ε2|gm|i2|gα+↓|g2|gm |πsets
8808 of values mod|42, hence the result set does also.
8817 In order to obtain all |ε2|gn |πpolynomials of
8825 degree |εn |πwith 0<1 coe∃cients, we need |εm|g2|4α+↓|42m|4|
8832 ¬R|4n.|'!!|1|1|πc)|9Set |εm|4|¬L|4|"l|¬H|v4n|)|"L
8835 |πand compute |εx|g2,|4x|g3,|4.|4.|4.|4,|4x|gm.
8838 |πLet |εu(x)|4α=↓|4u|βm|βα+↓|β1(x)x|g(|gm|gα+↓|g1|g)|gm|4α+↓
8839 |4αo↓|4αo↓|4αo↓|4α+↓|4u|β1(x)x|gm|4α+↓|4u|β0(x),
8840 |πwhere each |εu|βj(x) |πis a polynomial of degree
8848 |ε|→|¬Em |πwith integer coe∃cients (hence it
8854 can be evaluated without any more multiplications).
8861 Now evaluate |εu(x) |πby rule (2) as a polynomial
8870 in |εx|gm |πwith known coe∃cients. (The number
8877 of additions used is approximately the sum of
8885 the absolute values of the coe∃cients, so this
8893 algorithm is e∃cient on 0<1 polynomials. Paterson
8900 and Stockmeyer also gave another algorithm which
8907 uses about |ε|¬H|v42n|) |πmultiplications.|'!!|1|1!!|1|1Refe
8911 rence: |εIEEE Symp. Switching and Automata Theory
8918 |π|≡1|≡2 (1971), 140<143. R. J. Lipton has found
8926 0<1 polynomials that require |εc|=|g4|¬H|v4n|)/|πlog|4|εn
8931 |πchain multiplications even after complex preconditioning
8937 [|εIEEE Symp. Found. Comp. Sci. |π|≡1|≡6 (1975),
8944 6<10].|'{A3}|≡4|≡3|≡.|9|4When |εa|βi|4α=↓|4a|βj|4α+↓|4a|βk
8947 |πis a step in some optimal addition chain for
8956 |εn|4α+↓|41, |πcompute |εx|gi|4α=↓|4x|gjx|gk
8959 |πand |εp|βi↓α=↓|4p|βkx|gj|4α+↓|4p|βj, |πwhere
8962 |εp|βi|4α=↓|4x|gi|gα_↓|g1|4α+↓|4αo↓|4αo↓|4αo↓|4α+↓|4x|4α+↓|4
8962 1; |πomit the _nal calculation of |εx|gn|gα+↓|g1.
8969 |πWe save one multiplication whenever |εa|βk|4α=↓|41,
8975 |πin particular when |εi|4α=↓|41. |π({H9}|πCf.
8980 exercise 4.6.3<31 with |ε|≤e|4α=↓|4|f1|d32|).)|'
8984 {A24}{H10}|∨S|∨E|∨C|∨T|∨I|∨O|∨N |∨4|∨.|∨7|'{A12}{H9}|9|1|≡1|
8986 ≡.|9|4Find the _rst nonzero coe∃cient |εV|βm,
8992 |πas in (4), and divide both |εU(z) |πand |εV(z)
9001 |πby shifting |εz|gm (|πshifting the coe∃cients
9007 |εm |πplaces to the left). The quotient will
9015 be a power series i= |εU|β0|4α=↓|4αo↓|4αo↓|4αo↓|4α=↓|4U|βm|β
9020 α_↓|β1|4α=↓|40.|'{A3}|9|1|≡2|≡.|9|4|εV|urnα+↓1|)0|)W|βn|4α=↓
9021 |4V|urn|)0|)U|βn|4α_↓|4(V|ur1|)0|)W|β0)(V|urnα_↓1|)0|)V|βn)|
9021 4α_↓|4(V|ur2|)0|)W|β1)(V|urnα_↓2|)0|)V|βn|βα_↓|β1)|4α_↓|4αo↓
9021 |4αo↓|4αo↓|4α_↓|4(V|urn|β0|βW|βn|βα_↓|β1)(V|ur0|)0|)V|β1).
9022 |πThus, we start by replacing |ε(U|βj,|4V|βj)
9028 |πby (|εV|urj|)0|)U|βj,|4V|urjα_↓1|)0|)V|βj)
9030 |πfor |εj|4|¬R|41, |πthen set |εW|βn|4|¬L|4U|βn|4α_↓|4|¬K|ur
9034 |)0|¬Ek|¬Wn|)|4W|βkV|βn|βα_↓|βk |πfor |εn|4|¬R|40,
9037 |π_nally replace |εW|βj |πby |εW|βj/V|urjα+↓1|)0|)
9042 |πfor |εj|4|¬R|40. |πSimilar techniques can be
9048 used for other algorithms in this section.|'{A3}|9|1|≡3|≡.|9
9055 |4Yes. When |ε|≤a|4α=↓|40, |πit is easy to prove
9063 by induction that |εW|β1|4α=↓|4W|β2|4α=↓|4αo↓|4αo↓|4αo↓|4α=↓
9066 |40. |πWhen |ε|≤a|4α=↓|41, |πwe _nd |εW|βn|4α=↓|4V|βn,
9072 |πby the ``cute'' identity|'{A9}|↔k|uc|)|ε1|¬Ek|¬En|)|1|1|↔a
9076 |(k|4α_↓|4(n|4α_↓|4k)|d2n|)|↔s|1V|βkV|βn|βα_↓|βk|4α=↓|4V|β0V
9076 |βn.|;{A9}|9|1|≡4|≡.|9|4|πIf |εW(z)|4α=↓|4e|gV|g(|gz|g),
9079 |πthen |εW|¬S(z)|4α=↓|4V|¬S(z)W(z); |πwe _nd
9083 |εW|β0|4α=↓|41, |πand|'{A9}|εW|βn|4α=↓|4|↔k|uc|)1|¬Ek|¬En|)|
9085 4|(k|d2n|)|4V|βkW|βn|βα_↓|βk,!!|πfor!!|εn|4|¬R|41.|;
9086 {A9}|πIf |εW(z)|4α=↓|4|πln{H11}({H9}|ε1|4α+↓|4V(z){H11}){H9}
9087 , |πthen |εW|¬S(z)|4α+↓|4W|¬S(z)V(z)|4α=↓|4V|¬S(z);
9090 |πthe rule is |εW|β0|4α=↓|40, |πand |εW|β1|4α+↓|42W|β2z|4α+↓
9095 |4αo↓|4αo↓|4αo↓|4α=↓|4V|¬S(z)/{H11}({H9}1|4α+↓|4V(z){H11}){H
9095 9}.|'!!|1|1(|πBy exercise 6, the logarithm can
9102 be obtained to order |εn |πin |εO(n|4|πlog|4|εn)
9109 |πoperations. R. P. Brent observes that exp{H11}({H9}|εV(z){
9115 H11}){H9} |πcan also be calculated with this
9122 asymptotic speed by applying Newton's method
9128 to |εf(x)|4α=↓|4|πln|4|εx|4α_↓|4V(z); |πtherefore
9131 {H11}({H9}1|4α+↓|4|εV(z){H11}){H9}|g|≤a|4α=↓|4|πexp{H11}({H9
9131 }|ε|≤a|4|πln(1|4α+↓|4|εV(z)){H11}){H9} |πis |εO(n|4|πlog|4|ε
9133 n) |πtoo. |ε[Analytic Computational Complexity,
9138 |πed. by J. F. Traub (New York: Academic Press,
9147 1975), !|4|4|4<!|4|4|4.])|'{A3}|9|1|≡5|≡.|9|4We
9150 get the original series back again. This can
9158 be used to test a reversion algorithm.|'{A3}|9|1|≡6|≡.|9|4|ε
9165 |≤'(x)|4α=↓|4x|4α+↓|4x{H11}({H9}1|4α_↓|4xV(z){H11}){H9},
9166 |πcf. Algorithm 4.3.3R. Thus after |εW|β0,|4.|4.|4.|4,|4W|βN
9171 |βα_↓|β1 |πare known, we input |εV|βN,|4.|4.|4.|4,|4V|β2|βN|
9176 βα_↓|β1, |πcompute (|εW|β0|4α+↓|4αo↓|4αo↓|4αo↓|4α+↓|4W|βN|βα
9178 _↓|β1z|gN|gα_↓|g1)(V|β0|4α+↓|4αo↓|4αo↓|4αo↓|4α+↓|4V|β2|βN|βα
9178 _↓|β1z|g2|gN|gα_↓|g1)|4α=↓|41|4α+↓|4R|β0z|gN|4α+↓|4αo↓|4αo↓|
9178 4αo↓|4α+↓|4R|βN|βα_↓|β1z|g2|gN|gα_↓|g1|4α+↓|4O(z|g2|gN),
9179 |πand determine |εW|βN,|4.|4.|4.|4,|4W|β2|βN|βα_↓|β1
9182 |πby the formula |εW|βN|4α+↓|4αo↓|4αo↓|4αo↓|4α+↓|4W|β2|βN|βα
9185 _↓|β1z|gN|gα_↓|g1|4α=↓|4|→α_↓(W|β0|4α+↓|4αo↓|4αo↓|4αo↓|4α+↓|
9185 4W|βN|βα_↓|β1z|gN|gα_↓|g1)(R|β0|4α+↓|4αo↓|4αo↓|4αo↓|4α+↓|4R|
9185 βN|βα_↓|β1z|gN|gα_↓|g1)|4α+↓|4O(z|gN). [Numer.
9187 Math. |≡2|≡2 (1974), 341<348; |πthis algorithm
9193 was, in essence, _rst published by M. Sieveking,
9201 |εComputing |≡1|≡0 (|π1972), 153<156.] Note that
9207 the total time for |εN |πcoe∃cients is |εO(N|4|πlog|4|εN)
9215 |πif we use ``fast'' polynomial multiplication
9221 (exercise 4.6.4<14).|'{A3}|9|1|≡7|≡.|9|4|εW|βn|4α=↓|4(|fmk|d
9223 5k|))/n |πwhen |εn|4α=↓|4(m|4α_↓|41)k|4α+↓|41,
9226 |πotherwise 0. (Cf. exercise 2.3.4.4<11.)|'|Ha*?{U0}{H9L11M29
folio 842 galley 10
9231 }|πW58320#Computer|4Programming!(Knuth/Addison-Wesley)!Answe
9231 rs!f.|4842!g.|410d|'{A6}|9|1|≡8|≡.|9|4Input |εG|β1
9234 |πin step L1, and |εG|βn |πin step L2. In step
9244 L4, the output should be (|εU|βn|βα_↓|β1G|β1|4α+↓|42U|βn|βα_
9249 ↓|β2G|β2|4α+↓|4αo↓|4αo↓|4αo↓|4α+↓|4nU|β0G|βn)/n.
9250 (|πThe running time of the order |εN|g3 |πalgorithm
9258 is hereby increased by only order |εN|g2. |πThe
9266 value |εW|β1|4α=↓|4G|β1 |πmight be output in
9272 step L1.)|'!!|1|1|ε|*/Note:|\ |πAlgorithms T and
9278 N determine |εV|gα_↓|g1{H11}({H9}U(z){H11});
9281 |πthe algorithm in this exercise determines |εG{H11}({H9}V|g
9287 α_↓|g1(z){H11}){H9}, |πwhich is somewhat di=erent.
9292 Of course, the results can all be obtained by
9301 a sequence of operations of reversion and composition
9309 (exercise 11), but it is helpful to have more
9318 direct algorithms for each case.|'{A3}|9|1|≡9|≡.|E|'
9324 |\∂!!|2|hT|β1|βn|n|∂!n|4α=↓|41!|∂!n|4α=↓|42!|∂!n|4α=↓|43!|∂!
9324 n|4α=↓|44!|∂!n|4α=↓|45!|∂|'{A3}|>!!|2T|β1|βn|'
9327 1|;1|;2|;5|;14|;>|>!!|2T|β2|βn|'|'1|;2|;5|;14|;
9340 >|>!!|2T|β3|βn|'|'|'1|;3|;|9|19|;>|>!!|2T|β4|βn|'
9351 |'|'|'1|;|9|14|;>|>!!|2T|β5|βn|'|'|'|'|'|9|11|;
9364 >{A3}|π|≡1|≡0|≡.|9|4Form |εy|g1|g/|g|≤a|4α=↓|4x(1|4α+↓|4a|β1
9366 x|4α+↓|4a|β2x|g2|4α+↓|4αo↓|4αo↓|4αo↓)|g1|g/|g|≤a|4α=↓|4x(1|4
9366 α+↓|4c|β1x|4α+↓|4c|β2x|g2|4α+↓|4αo↓|4αo↓|4αo↓)
9367 |πby means of (9); |πthen revert the latter series.
9376 (See the remarks following Eq. 1.2.11.3<11.)|'
9382 {A3}|≡1|≡1|≡.|9|4Set |εW|β0|4|¬L|4U|β0, |πand
9385 set |ε(T|βk,|4W|βk)|4|¬L|4(V|βk,|40) |πfor 1|4|¬E|4|εk|4|¬E|
9388 4N. |πThen for |εn|4α=↓|41, 2,|4.|4.|4.|4,|4N,
9393 |πdo the following: Set |εW|βj|4|¬L|4W|βj|4α+↓|4U|βnT|βj
9398 |πfor |εn|4|¬E|4j|4|¬E|4N; |πand then set |εT|βj|4|¬L|4T|βj|
9403 βα_↓|β1V|β1|4α+↓|4αo↓|4αo↓|4αo↓|4α+↓|4T|βnV|βj|βα_↓|βn
9404 |πfor |εj|4α=↓|4N, N|4α_↓|41,|4.|4.|4.|4,|4n|4α+↓|41.|'
9407 !!|2|πHere |εT(z) |πrepresents |εV(z)|gn. |πAn
9412 |εon-line |πpower-series algorithm for this problem,
9418 |πanalogous to Algorithm T, could be constructed,
9425 but it would require about |εN|g2/2 |πstorage
9432 locations. There is also an on-line algorithm
9439 which solves this exercise and needs only |εO(N)
9447 |πstorage locations: |πWe may assume that |εV|β1|4α=↓|41,
9454 |πif |εU|βk |πis replaced by |εU|βkV|urk|)1|)
9460 |πand |εV|βk |πis replaced by |εV|βk/V|β1 |πfor
9467 all |εk. |πThen we may revert |εV(z) |πby Algorithm
9476 L, using it soutput as input to the algorithm
9485 of exercise 8 with |εG|β1|4α=↓|4U|β1, G|β2|4α=↓|4U|β2,
9491 |πetc., thus computing |εU{H11}({H9}(V|gα_↓|g1)|gα_↓|g1(z){H
9494 11}){H9}|4α_↓|4U|β0.|'!!|2|πBrent and Kung have
9499 constructed several algorithms which are asymptotically
9505 faster. For example, we can evaluate |εU(x) |πfor
9513 |εx|4α=↓|4V(z) |πby a slight variant of exercise
9520 4.6.4<42(c), doing about 2|¬H|v4|εn|) |πchain
9525 multiplications of cost |εM(n) |πand about |εn
9532 |πparameter multiplications of cost |εn; |πthe
9538 total time is therefore |εO{H11}({H9}|¬H|v4n|)M(n)|4α+↓|4n|g
9542 2{H11}){H9}|4α=↓|4O(n|g2). |πA still faster method
9547 can be based on the identity |εU{H11}({H9}V|β0(z)|4α+↓|4z|gm
9553 V|β1(z){H11}){H9}|4α=↓|4U{H11}({H9}V|β0(z){H11}){H9}|4α+↓|4z
9553 |gmU|¬S{H11}({H9}V|β0(z){H11}){H9}V|β1(z)|4α+↓|4z|g2|gmU|≤C{
9553 H11}({H9}V|β0(z){H11}){H9}V|β1(z){H11}){H9}V|β1(z)|g2/2*3|4α+
9553 ↓|4αo↓|4αo↓|4αo↓|4, |πextending to about |εn/m
9558 |πterms, where we choose |εm|4|¬V|4|¬H|v4n/|πlog|4|εn|);
9563 |πthe _rst term |εU{H11}({H9}V|β0(z){H11}){H9}
9567 |πis evaluated in |εO{H11}({H9}mn(|πlog|4|εn){H11}){H9}|g2)
9571 |πoperations using a method somewhat like that
9578 in exercise 4.6.4<43, |πand {H11}({H9}since we
9584 can go from |εU|g(|gk|g){H11}({H9}V|β0(z){H11}){H9}
9588 |πto |εU|g(|gk|gα+↓|g|≤n|g){H11}({H9}V|β0(z){H11}){H9}
9590 |πin |εO(n|4|πlog|4|εn) |πoperations by di=erentiating
9595 and dividing by |εV|ur|↔0|)1|)(z){H11}){H9} |πthe
9600 entire procedure takes |εO{H11}({H9}mn(|πlog|4|εn)|g2|4α+↓|4
9603 (n/m)n|4|πlog|4|εn)|4α=↓|4O(n|4|πlog|4|εn)|g3|g/|g2
9604 |πoperations.|'{A3}|≡1|≡2|≡.|9|4Polynomial division
9607 is trivial unless |εm|4|¬R|4n|4|¬R|41. |πAssuming
9612 the latter, the equation |εu(x)|4α=↓|4q(x)v(x)|4α+↓|4r(x)
9617 |πis equivalent to |εU(z)|4α=↓|4Q(z)V(z)|4α+↓|4z|gm|gα_↓|gn|
9620 gα+↓|g1R(z) |πwhere |εU(x)|4α=↓|4x|gmu(x|gα_↓|g1),
9623 V(x)|4α=↓|4x|gnv(x|gα_↓|g1), Q(x)|4α=↓|4x|gm|gα_↓|gnq(x|gα_↓
9624 |g1), R(x)|4α=↓|4x|gn|gα_↓|g1r(x|gα_↓|g1) |πare
9627 the ``reverse'' polynomials of |εu, v, q, |πand
9635 |εr.|'!!|1|1|πTo _nd |εq(x) |πand |εr(x), |πcompute
9642 the _rst |εm|4α_↓|4n|4α+↓|41 |πcoe∃cients of
9647 the power series |εU(z)/V(z)|4α=↓|4W(z)|4α+↓|4O(z|gm|gα_↓|gn
9650 |gα+↓|g1); |πthen compute the power series |εU(z)|4α_↓|4V(z)
9656 W(z), |πwhich has the form |εz|gm|gα_↓|gn|gα+↓|g1T(z)
9662 |πwhere |εT(z)|4α=↓|4T|β0|4α+↓|4T|β1z|4α+↓|4αo↓|4αo↓|4αo↓|4.
9663 |πNote that |εT|βj|4α=↓|40 |πfor all |εj|4|¬R|4n;
9670 |πhence |εQ(z)|4α=↓|4W(z) |πand |εR(z)|4α=↓|4T(z)
9674 |πsatisfy the requirements.|'{A25}{H11}|!A|1|1|!P|1|1|!P|1|1
9677 |!E|1|1|!N|1|1|!D|1|1|!I|1|1|!X|4|4|4|!A|'{A49}{A9}{H20L22}|
9678 ∨T|∨A|∨B|∨L|∨E|∨S|9|∨O|∨F|?|∨N|∨U|∨M|∨E|∨R|∨I|∨C|∨A|∨L|9|∨Q|
9679 ∨U|∨A|∨N|∨T|∨I|∨T|∨I|∨E|∨S|?{A12}{H8L10}|∨T|∨a|∨b|∨l|∨e|4|4|
9680 ∨1|;{A6}{H9L11}{M22}QUANTITIES WHICH ARE FREQUENTLY
9685 USED IN STANDARD SUBROUTINES AND IN ANALYSIS
9692 OF COMPUTER PROGRAMS. (40 DECIMAL PLACES)|;|J#>
9699 {M32}|ε|h|¬H|≤p|3α=↓|3|≤)(1/2)|4|∂α=↓|4!!|E|n|'
9700 | |¬H|v42|)|4|Lα=↓|41.41421|935623!73095|904880|916887|92420
9700 9|969807|985697|→α_↓>| |¬H|v43|)|4|Lα=↓|41.73205|908075|9688
9701 77|929352|974463|941505|987236|969428|→α+↓>| |¬H|v45|)|4|Lα=
9702 ↓|42.23606|979774|999789|969640|991736|968731|917623|954406|
9702 →α+↓>| |¬H|v410|)|4|Lα=↓|43.16227|976601|968379|933199|98893
9703 5|944432|971853|937196|→α_↓>| |¬H|v42|)|4|Lα=↓|41.25992|9104
9704 98|994873|916476|972106|907278|922835|905703|→α_↓>
9705 | |¬H|v43|)|4|Lα=↓|41.44224|995703|907408|938232|916383|9107
9705 80|910958|983919|→α_↓>| |¬H|v42|)|4|Lα=↓|41.18920|971150|902
9706 721|906671|974999|970560|947591|952930|→α_↓>| |πln|42|4|Lα=↓
9707 |40.69314|971805|959945|930941|972321|921458|917656|980755|→
9707 α+↓>| ln|43|4|Lα=↓|41.09861|922886|968109|969139|952452|9369
9708 22|952570|946475|→α_↓>| ln|410|4|Lα=↓|42.30258|950929|994045
9709 |968401|979914|954684|936420|976011|→α+↓>| 1/ln|42|4|Lα=↓|41
9710 .44269|950408|988963|940735|999246|981001|989213|974266|→α+↓
9710 >| 1/ln|410|4|Lα=↓|40.43429|944819|903251|982765|911289|9189
9711 16|960508|922944|→α_↓>| |ε|≤p|4|Lα=↓|43.14159|926535|989793|
9712 923846|926433|983279|950288|941972|→α_↓>| 1|¬P|3α=↓|3|≤p/180
9713 |4|Lα=↓|40.01745|932925|919943|929576|992369|907684|988612|9
9713 71344|→α+↓>| 1/|≤p|4|Lα=↓|40.31830|998861|983790|967153|9776
9714 75|926745|902872|940689|→α+↓>| |≤p|g2|4|Lα=↓|49.86960|944010
9715 |989358|961883|944909|999876|915113|953137|→α_↓>
9716 | |¬H|v4|≤p|)|3|4α=↓|3|≤)(1/2)|4|Lα=↓|41.77245|938509|905516
9716 |902729|981674|983341|914518|927975|→α+↓>| |≤)(1/3)|4|Lα=↓|4
9717 2.67893|985347|907747|963365|956929|940974|967764|941287|→α_
9717 ↓>| |≤)(2/3)|4|Lα=↓|41.35411|979394|926400|941694|952880|928
9718 154|951378|955193|→α+↓>| |εe|4|Lα=↓|42.71828|918284|959045|9
9719 23536|902874|971352|966249|977572|→α+↓>| 1/e|4|Lα=↓|40.36787
9720 |994411|971442|932159|955237|970161|946086|974458|→α+↓>
9721 | e|g2|4|Lα=↓|47.38905|960989|930650|922723|904274|960575|90
9721 0781|931803|→α+↓>| |≤g|4|Lα=↓|40.57721|956649|901532|986060|
9722 965120|990082|940243|910422|→α_↓>| |πln|4|ε|≤p|4|Lα=↓|41.144
9723 72|998858|949400|917414|934273|951353|905871|916473|→α_↓>
9724 | |≤f|4|Lα=↓|41.61803|939887|949894|984820|945868|934365|963
9724 811|977203|→α+↓>| e|g|≤g|4|Lα=↓|41.78107|924179|990197|99852
9725 3|965041|903107|917954|991696|→α+↓>| e|g|≤p|g/|g4|4|Lα=↓|42.
9726 19328|900507|938015|945655|997696|959278|973822|934616|→α+↓>
9727 | |πsin|41|4|Lα=↓|40.84147|909848|907896|950665|925023|92163
9727 0|929899|996226|→α_↓>| cos|41|4|Lα=↓|40.54030|923058|968139|
9728 971740|909366|907442|997660|937323|→α+↓>| |ε|≤z(3)|4|Lα=↓|41
9729 .20205|969031|959594|928539|997381|961511|944999|907650|→α_↓
9729 >| |πln|4|ε|≤f|4|Lα=↓|40.48121|918250|959603|944749|977589|9
9730 13424|936842|931352|→α_↓>| 1/|πln|4|ε|≤f|4|Lα=↓|42.07808|969
9731 212|935027|953760|913226|906117|979576|977422|→α_↓>
9732 | |→α_↓|πln|4ln|42|4|Lα=↓|40.36651|929205|981664|932701|9243
9732 91|958232|966946|994543|→α_↓>{B2}|J#>{A6}|Ha{U0}{H9L11M29}|π
folio 844 galley 11 "special italic figs in position 4"
9734 W58320#Computer|4Programming!(Knuth/Addison-Wesley)!Appendix
9734 !f.|4844!g.|411d|'{A12}{H8L10}|∨T|∨a|∨b|∨l|∨e|7|∨2|;
9736 {A6}{H9L11}QUANTITIES WHICH ARE FREQUENTLY USED
9741 IN STANDARD SUBROUTINES AND IN ANALYSIS OF COMPUTER
9749 PROGRAMS, IN |εOCTAL |πNOTATION. THE |εNAME |πOF
9756 EACH QUANTITY, APPEARING AT THE LEFT OF THE EQUAL
9765 SIGN, IS GIVEN IN DECIMAL NOTATION.|;|J#>!!!!!!0.1|4|∂α=↓|4|
9772 */|↔0.|↔0|↔6|↔3|↔1|↔4|9|↔6|↔3|↔1|↔4|↔6|9|↔3|↔1|↔4|↔6|↔3|9|↔1|
9772 ↔4|↔6|↔3|↔1|9|↔4|↔6|↔3|↔1|↔4|9|↔6|↔3|↔1|↔4|↔6|9|↔3|↔1|↔4|↔6|
9772 ↔3|9|↔1|↔4|↔6|↔3|↔1|9|↔4|↔6|↔3|↔2|'| |\0.01|4|Lα=↓|4|*/|↔0.|↔
9773 0|↔0|↔5|↔0|↔7|9|↔5|↔3|↔4|↔1|↔2|9|↔1|↔7|↔2|↔7|↔0|9|↔2|↔4|↔3|↔
9773 6|↔5|9|↔6|↔0|↔5|↔0|↔7|9|↔5|↔3|↔4|↔1|↔2|9|↔1|↔7|↔2|↔7|↔0|9|↔2
9773 |↔4|↔3|↔6|↔5|9|↔6|↔0|↔5|↔1|\>| 0.001|4|Lα=↓|4|*/|↔0.|↔0|↔0|↔0
9774 |↔4|↔0|9|↔6|↔1|↔1|↔1|↔5|9|↔6|↔4|↔5|↔7|↔0|9|↔6|↔5|↔1|↔7|↔6|9|
9774 ↔7|↔6|↔3|↔5|↔5|9|↔4|↔4|↔2|↔6|↔4|9|↔1|↔6|↔2|↔5|↔4|9|↔0|↔2|↔0|
9774 ↔3|↔0|9|↔4|↔4|↔6|↔7>| |\0.0001|4|Lα=↓|4|*/|↔0.|↔0|↔0|↔0|↔0|↔3
9775 |9|↔2|↔1|↔5|↔5|↔6|9|↔1|↔3|↔5|↔3|↔0|9|↔7|↔0|↔4|↔1|↔4|9|↔5|↔4|
9775 ↔5|↔1|↔2|9|↔7|↔5|↔1|↔7|↔0|9|↔3|↔3|↔0|↔2|↔1|9|↔1|↔5|↔0|↔0|↔2|
9775 9|↔3|↔5|↔2|↔2|\>| 0.00001|4|Lα=↓|4|*/|↔0.|↔0|↔0|↔0|↔0|↔0|9|↔2
9776 |↔4|↔7|↔6|↔1|9|↔3|↔2|↔6|↔1|↔0|9|↔7|↔0|↔6|↔6|↔4|9|↔3|↔6|↔0|↔4
9776 |↔1|9|↔0|↔6|↔0|↔7|↔7|9|↔1|↔7|↔4|↔0|↔1|9|↔5|↔6|↔0|↔6|↔3|9|↔3|
9776 ↔4|↔4|↔2>| |\0.000001|4|Lα=↓|4|*/|↔0.|↔0|↔0|↔0|↔0|↔0|9|↔0|↔2|
9777 ↔0|↔6|↔1|9|↔5|↔7|↔3|↔6|↔5|9|↔0|↔5|↔5|↔3|↔6|9|↔6|↔6|↔1|↔5|↔1|
9777 9|↔5|↔5|↔3|↔2|↔3|9|↔0|↔7|↔7|↔4|↔6|9|↔4|↔4|↔4|↔7|↔0|9|↔2|↔6|↔
9777 0|↔3|\>| 0.0000001|4|Lα=↓|4|*/|↔0.|↔0|↔0|↔0|↔0|↔0|9|↔0|↔0|↔1|
9778 ↔5|↔3|9|↔2|↔7|↔7|↔4|↔5|9|↔1|↔5|↔2|↔7|↔4|9|↔5|↔3|↔6|↔4|↔4|9|↔
9778 1|↔2|↔7|↔4|↔1|9|↔7|↔2|↔3|↔1|↔2|9|↔2|↔0|↔3|↔5|↔4|9|↔0|↔2|↔1|↔
9778 5>| |\0.00000001|4|Lα=↓|4|*/|↔0.|↔0|↔0|↔0|↔0|↔0|9|↔0|↔0|↔0|↔1
9779 |↔2|9|↔5|↔7|↔1|↔4|↔3|9|↔5|↔6|↔1|↔0|↔6|9|↔0|↔4|↔3|↔0|↔3|9|↔4|
9779 ↔7|↔3|↔7|↔4|9|↔7|↔7|↔3|↔4|↔1|9|↔0|↔1|↔5|↔1|↔2|9|↔6|↔3|↔3|↔3>
9780 | |\0.000000001|4|Lα=↓|4|*/|↔0.|↔0|↔0|↔0|↔0|↔0|9|↔0|↔0|↔0|↔0|
9780 ↔1|9|↔0|↔4|↔5|↔6|↔0|9|↔2|↔7|↔6|↔4|↔0|9|↔4|↔6|↔6|↔5|↔5|9|↔1|↔
9780 2|↔2|↔6|↔2|9|↔7|↔1|↔4|↔2|↔6|9|↔4|↔0|↔1|↔2|↔4|9|↔2|↔1|↔7|↔4>
9781 | |\0.0000000001|4|Lα=↓|4|*/|↔0.|↔0|↔0|↔0|↔0|↔0|9|↔0|↔0|↔0|↔0
9781 |↔0|9|↔0|↔6|↔6|↔7|↔6|9|↔3|↔3|↔7|↔6|↔6|9|↔3|↔5|↔3|↔6|↔7|9|↔5|
9781 ↔5|↔6|↔5|↔3|9|↔3|↔7|↔2|↔6|↔5|9|↔3|↔4|↔6|↔4|↔2|9|↔0|↔1|↔6|↔3>
9782 | |\|¬H2|4|Lα=↓|4|*/|↔1.|↔3|↔2|↔4|↔0|↔4|9|↔7|↔4|↔6|↔3|↔1|9|↔7
9782 |↔7|↔1|↔6|↔7|9|↔4|↔6|↔2|↔2|↔0|9|↔4|↔2|↔6|↔2|↔7|9|↔6|↔6|↔1|↔1
9782 |↔5|9|↔4|↔6|↔7|↔2|↔5|9|↔1|↔2|↔5|↔7|↔5|9|↔1|↔7|↔4|↔4|\>
9783 | |¬H3|4|Lα=↓|4|*/|↔1.|↔5|↔6|↔6|↔6|↔3|9|↔6|↔5|↔6|↔4|↔1|9|↔3|↔
9783 0|↔2|↔3|↔1|9|↔2|↔5|↔1|↔6|↔3|9|↔5|↔4|↔4|↔5|↔3|9|↔5|↔0|↔2|↔6|↔
9783 5|9|↔6|↔0|↔3|↔6|↔1|9|↔3|↔4|↔0|↔7|↔3|9|↔4|↔2|↔2|↔2|\>
9784 | |¬H5|4|Lα=↓|4|*/|↔2.|↔1|↔7|↔0|↔6|↔7|9|↔3|↔6|↔3|↔3|↔4|9|↔5|↔
9784 7|↔7|↔2|↔2|9|↔4|↔7|↔6|↔0|↔2|9|↔5|↔7|↔4|↔7|↔1|9|↔6|↔3|↔0|↔0|↔
9784 3|9|↔0|↔0|↔5|↔6|↔3|9|↔5|↔5|↔6|↔2|↔0|9|↔3|↔2|↔0|↔2|\>
9785 | |¬H10|4|Lα=↓|4|*/|↔3.|↔1|↔2|↔3|↔0|↔5|9|↔4|↔0|↔7|↔2|↔6|9|↔6|
9785 ↔4|↔5|↔5|↔5|9|↔2|↔2|↔4|↔4|↔4|9|↔0|↔2|↔2|↔4|↔2|9|↔5|↔7|↔1|↔0|
9785 ↔1|9|↔4|↔1|↔4|↔6|↔6|9|↔3|↔3|↔7|↔7|↔5|9|↔2|↔2|↔5|↔3|\>
9786 | |¬H2|4|Lα=↓|4|*/|↔1.|↔2|↔0|↔5|↔0|↔5|9|↔0|↔5|↔7|↔4|↔6|9|↔1|↔
9786 5|↔3|↔4|↔5|9|↔0|↔5|↔3|↔4|↔2|9|↔1|↔0|↔7|↔5|↔6|9|↔6|↔5|↔3|↔3|↔
9786 4|9|↔2|↔5|↔5|↔7|↔4|9|↔2|↔2|↔4|↔1|↔5|9|↔0|↔3|↔0|↔3|\>
9787 | |¬H3|4|Lα=↓|4|*/|↔1.|↔3|↔4|↔2|↔3|↔3|9|↔5|↔0|↔4|↔4|↔4|9|↔2|↔
9787 2|↔1|↔7|↔5|9|↔7|↔3|↔1|↔3|↔4|9|↔6|↔7|↔3|↔6|↔3|9|↔7|↔6|↔1|↔3|↔
9787 3|9|↔0|↔5|↔3|↔3|↔4|9|↔3|↔1|↔1|↔4|↔7|9|↔6|↔0|↔1|↔2|\>
9788 | |¬H2|4|Lα=↓|4|*/|↔1.|↔1|↔4|↔0|↔6|↔7|9|↔7|↔4|↔0|↔5|↔0|9|↔6|↔
9788 1|↔5|↔5|↔6|9|↔1|↔2|↔4|↔5|↔5|9|↔7|↔2|↔1|↔5|↔2|9|↔6|↔4|↔4|↔3|↔
9788 0|9|↔6|↔0|↔2|↔7|↔1|9|↔0|↔2|↔7|↔5|↔5|9|↔7|↔3|↔1|↔4|\>
9789 | ln|42|4|Lα=↓|4|*/|↔0.|↔5|↔4|↔2|↔7|↔1|9|↔0|↔2|↔7|↔7|↔5|9|↔7|
9789 ↔5|↔0|↔7|↔1|9|↔7|↔3|↔6|↔3|↔2|9|↔5|↔7|↔1|↔1|↔7|9|↔0|↔7|↔3|↔1|
9789 ↔6|9|↔3|↔0|↔0|↔0|↔7|9|↔7|↔1|↔3|↔6|↔6|9|↔5|↔3|↔6|↔4|\>
9790 | ln|43|4|Lα=↓|4|*/|↔1.|↔0|↔6|↔2|↔3|↔7|9|↔2|↔4|↔7|↔5|↔2|9|↔5|
9790 ↔5|↔0|↔0|↔6|9|↔0|↔5|↔2|↔2|↔7|9|↔3|↔2|↔4|↔4|↔0|9|↔6|↔3|↔0|↔6|
9790 ↔5|9|↔2|↔5|↔0|↔1|↔2|9|↔3|↔5|↔5|↔7|↔4|9|↔5|↔5|↔3|↔4|\>
9791 | ln|43|4|Lα=↓|4|*/|↔2.|↔2|↔3|↔2|↔7|↔3|9|↔0|↔6|↔7|↔3|↔5|9|↔5|
9791 ↔2|↔5|↔2|↔4|9|↔2|↔5|↔4|↔0|↔5|9|↔5|↔6|↔5|↔1|↔2|9|↔6|↔6|↔5|↔4|
9791 ↔2|9|↔5|↔6|↔0|↔2|↔6|9|↔4|↔6|↔0|↔5|↔0|9|↔5|↔0|↔7|↔1|\>
9792 | 1/ln|42|4|Lα=↓|4|*/|↔1.|↔3|↔4|↔2|↔5|↔2|9|↔1|↔6|↔6|↔2|↔4|9|↔
9792 5|↔3|↔4|↔0|↔5|9|↔7|↔7|↔0|↔2|↔7|9|↔3|↔5|↔7|↔5|↔0|9|↔3|↔7|↔7|↔
9792 6|↔6|9|↔4|↔0|↔6|↔4|↔4|9|↔3|↔5|↔1|↔7|↔5|9|↔0|↔4|↔3|↔5|\>
9793 | 1/ln|410|4|Lα=↓|4|*/|↔0.|↔3|↔3|↔6|↔2|↔6|9|↔7|↔5|↔4|↔2|↔5|9|
9793 ↔1|↔1|↔5|↔6|↔2|9|↔4|↔1|↔6|↔1|↔4|9|↔5|↔2|↔3|↔2|↔5|9|↔2|↔7|↔6|
9793 ↔5|↔5|9|↔1|↔4|↔7|↔5|↔6|9|↔0|↔6|↔2|↔2|\>| |ε|≤p|4|Lα=↓|4|*/|↔3
9794 .|↔1|↔1|↔0|↔3|↔7|9|↔5|↔5|↔2|↔4|↔2|9|↔1|↔0|↔2|↔6|↔4|9|↔3|↔0|↔
9794 2|↔1|↔5|9|↔1|↔4|↔2|↔3|↔0|9|↔6|↔3|↔0|↔5|↔0|9|↔5|↔6|↔0|↔0|↔6|9
9794 |↔7|↔0|↔1|↔6|↔3|9|↔2|↔1|↔1|↔2|\>| 1|¬P|4α=↓|4|≤p/180|4|Lα=↓|
9795 4|*/|↔0.|↔0|↔1|↔0|↔7|↔3|9|↔7|↔2|↔1|↔5|↔2|9|↔1|↔1|↔2|↔2|↔4|9|↔
9795 7|↔2|↔3|↔4|↔4|9|↔2|↔5|↔6|↔0|↔3|9|↔5|↔4|↔2|↔7|↔6|9|↔6|↔3|↔3|↔
9795 5|↔1|9|↔2|↔2|↔0|↔5|↔6|9|↔1|↔1|↔5|↔5|\>| 1/|≤p|4|Lα=↓|4|*/|↔0|
9796 ↔.|↔2|↔4|↔2|↔7|↔6|9|↔3|↔0|↔1|↔5|↔5|9|↔6|↔2|↔3|↔4|↔4|9|↔2|↔0|
9796 ↔2|↔5|↔1|9|↔2|↔3|↔7|↔6|↔0|9|↔4|↔7|↔2|↔5|↔7|9|↔5|↔0|↔7|↔6|↔5|
9796 9|↔1|↔5|↔1|↔5|↔6|9|↔7|↔0|↔0|↔7|\>| |≤p|g2|4|Lα=↓|4|*/|↔1.|↔6|
9797 ↔7|↔5|↔1|↔7|9|↔1|↔4|↔4|↔6|↔7|9|↔6|↔2|↔1|↔3|↔5|9|↔7|↔1|↔3|↔2|
9797 ↔2|9|↔2|↔5|↔5|↔6|↔1|9|↔1|↔5|↔4|↔6|↔6|9|↔3|↔0|↔0|↔2|↔1|9|↔4|↔
9797 0|↔6|↔5|↔4|9|↔3|↔4|↔1|↔0>| |\|¬H|≤p|4α=↓|4|≤)(1/2)|4|Lα=↓|4|
9798 */|.|↔6|↔1|↔3|↔3|↔7|9|↔6|↔1|↔1|↔0|↔6|9|↔6|↔4|↔7|↔3|↔6|9|↔6|↔5
9798 |↔2|↔4|↔7|9|↔4|↔7|↔0|↔3|↔5|9|↔4|↔0|↔5|↔1|↔0|9|↔1|↔5|↔2|↔7|↔3
9798 |9|↔3|↔4|↔4|↔7|↔0|9|↔1|↔7|↔7|↔6|\>| |≤)(1/3)|4|Lα=↓|4|*/|↔2.|
9799 ↔5|↔3|↔3|↔4|↔7|9|↔3|↔5|↔2|↔3|↔4|9|↔5|↔1|↔0|↔1|↔3|9|↔6|↔1|↔3|
9799 ↔1|↔6|9|↔7|↔3|↔1|↔0|↔6|9|↔4|↔7|↔6|↔4|↔4|9|↔5|↔4|↔6|↔5|↔3|9|↔
9799 0|↔0|↔1|↔0|↔6|9|↔6|↔6|↔0|↔5|\>| |≤)(2/3)|4|Lα=↓|4|*/|↔1.|↔2|↔
9800 6|↔5|↔2|↔3|9|↔5|↔7|↔1|↔1|↔2|9|↔1|↔4|↔1|↔5|↔4|9|↔7|↔4|↔3|↔1|↔
9800 2|9|↔5|↔4|↔5|↔7|↔2|9|↔3|↔7|↔6|↔5|↔5|9|↔6|↔0|↔1|↔2|↔6|9|↔2|↔3
9800 |↔2|↔3|↔1|9|↔0|↔2|↔4|↔5|\>| e|4|Lα=↓|4|*/|↔2.|↔5|↔5|↔7|↔6|↔0|
9801 9|↔5|↔2|↔1|↔3|↔0|9|↔5|↔0|↔5|↔3|↔5|9|↔5|↔1|↔2|↔4|↔6|9|↔5|↔2|↔
9801 7|↔7|↔3|9|↔4|↔2|↔5|↔4|↔2|9|↔0|↔0|↔4|↔7|↔1|9|↔7|↔2|↔3|↔6|↔3|9
9801 |↔6|↔1|↔6|↔6|\>| 1/e|4|Lα=↓|4|*/|↔0.|↔2|↔7|↔4|↔2|↔6|9|↔5|↔3|↔
9802 0|↔6|↔6|9|↔1|↔3|↔1|↔6|↔7|9|↔4|↔6|↔7|↔6|↔1|9|↔5|↔2|↔7|↔2|↔6|9
9802 |↔7|↔5|↔4|↔3|↔6|9|↔0|↔2|↔4|↔4|↔0|9|↔5|↔2|↔3|↔7|↔1|9|↔0|↔3|↔3
9802 |↔6|\>| e|g2|4|Lα=↓|4|*/|↔7.|↔3|↔0|↔7|↔1|↔4|9|↔4|↔5|↔6|↔1|↔5|
9803 9|↔2|↔3|↔3|↔5|↔5|9|↔3|↔3|↔4|↔6|↔0|9|↔6|↔3|↔5|↔0|↔7|9|↔3|↔5|↔
9803 0|↔4|↔0|9|↔3|↔2|↔6|↔6|↔4|9|↔2|↔5|↔3|↔5|↔6|9|↔5|↔0|↔2|↔2|\>
9804 | |≤g|4|Lα=↓|4|*/|↔0.|↔4|↔4|↔7|↔4|↔2|9|↔1|↔4|↔7|↔7|↔0|9|↔6|↔7
9804 |↔6|↔6|↔6|9|↔0|↔6|↔1|↔7|↔2|9|↔2|↔3|↔2|↔1|↔5|9|↔7|↔4|↔3|↔7|↔6
9804 |9|↔0|↔1|↔0|↔0|↔2|9|↔5|↔1|↔3|↔1|↔3|9|↔2|↔5|↔5|↔2|\>
9805 | |πln|4|ε|≤p|4|Lα=↓|4|*/|↔1.|↔1|↔1|↔2|↔0|↔6|9|↔4|↔0|↔4|↔4|↔3
9805 |9|↔4|↔7|↔5|↔0|↔3|9|↔3|↔6|↔4|↔1|↔3|9|↔6|↔5|↔3|↔7|↔4|9|↔5|↔2|
9805 ↔6|↔6|↔1|9|↔5|↔2|↔4|↔1|↔0|9|↔3|↔7|↔5|↔1|↔1|9|↔4|↔6|↔0|↔6|\>
9806 | |≤f|4|Lα=↓|4|*/|↔1.|↔4|↔7|↔4|↔3|↔3|9|↔5|↔7|↔1|↔5|↔6|9|↔2|↔7
9806 |↔7|↔5|↔1|9|↔2|↔3|↔7|↔0|↔1|9|↔2|↔7|↔6|↔3|↔4|9|↔7|↔1|↔4|↔0|↔1
9806 |9|↔4|↔0|↔2|↔7|↔1|9|↔6|↔6|↔7|↔1|↔0|9|↔1|↔5|↔0|↔1|\>
9807 | e|g|≤g|4|Lα=↓|4|*/|↔1.|↔6|↔1|↔7|↔7|↔2|9|↔1|↔3|↔4|↔5|↔2|9|↔6
9807 |↔1|↔1|↔5|↔2|9|↔6|↔5|↔7|↔6|↔1|9|↔2|↔2|↔4|↔7|↔7|9|↔3|↔6|↔5|↔5
9807 |↔3|9|↔5|↔3|↔3|↔2|↔7|9|↔1|↔7|↔5|↔5|↔4|9|↔2|↔1|↔2|↔6|\>
9808 | e|g|≤p|g/|g4|4|Lα=↓|4|*/|↔2.|↔1|↔4|↔2|↔7|↔5|9|↔3|↔1|↔5|↔1|↔
9808 2|9|↔1|↔6|↔1|↔6|↔2|9|↔5|↔2|↔3|↔7|↔0|9|↔3|↔5|↔5|↔3|↔0|9|↔1|↔1
9808 |↔3|↔4|↔2|9|↔5|↔3|↔5|↔2|↔5|9|↔4|↔4|↔3|↔0|↔7|9|↔0|↔2|↔1|↔7|\>
9809 | |πsin|41|4|Lα=↓|4|*/|↔0.|↔6|↔5|↔6|↔6|↔5|9|↔2|↔4|↔4|↔3|↔6|9|
9809 ↔0|↔4|↔4|↔1|↔4|9|↔7|↔3|↔4|↔0|↔2|9|↔0|↔3|↔0|↔6|↔7|9|↔2|↔3|↔6|
9809 ↔4|↔4|9|↔1|↔1|↔6|↔1|↔2|9|↔0|↔7|↔4|↔7|↔4|9|↔1|↔4|↔5|↔1|\>
9810 | cos|41|4|Lα=↓|4|*/|↔0.|↔4|↔2|↔4|↔5|↔0|9|↔5|↔0|↔0|↔3|↔7|9|↔3
9810 |↔2|↔4|↔0|↔6|9|↔4|↔2|↔7|↔1|↔1|9|↔0|↔7|↔0|↔2|↔2|9|↔1|↔4|↔6|↔6
9810 |↔6|9|↔2|↔7|↔3|↔2|↔0|9|↔7|↔0|↔6|↔7|↔5|9|↔1|↔2|↔3|↔2|\>
9811 | |ε|≤z(3)|4|Lα=↓|4|*/|↔1.|↔1|↔4|↔7|↔3|↔5|9|↔0|↔0|↔0|↔2|↔3|9|
9811 ↔6|↔0|↔0|↔1|↔4|9|↔2|↔0|↔4|↔7|↔0|9|↔1|↔5|↔6|↔1|↔3|9|↔4|↔2|↔5|
9811 ↔6|↔1|9|↔3|↔1|↔7|↔1|↔5|9|↔1|↔0|↔1|↔7|↔7|9|↔0|↔6|↔6|↔2|\>
9812 | |πln|4|ε|≤f|4|Lα=↓|4|*/|↔0.|↔3|↔6|↔6|↔3|↔0|9|↔2|↔6|↔2|↔5|↔6
9812 |9|↔6|↔1|↔2|↔1|↔3|9|↔0|↔1|↔1|↔4|↔5|9|↔1|↔3|↔7|↔0|↔0|9|↔4|↔1|
9812 ↔0|↔0|↔4|9|↔5|↔2|↔2|↔6|↔4|9|↔3|↔0|↔7|↔0|↔0|9|↔4|↔0|↔6|↔5|\>
9813 | |π1/ln|4|ε|≤f|4|Lα=↓|4|*/|↔2.|↔0|↔4|↔7|↔7|↔6|9|↔6|↔0|↔1|↔1|
9813 ↔1|9|↔1|↔7|↔1|↔4|↔4|9|↔4|↔1|↔5|↔1|↔2|9|↔1|↔1|↔4|↔3|↔6|9|↔1|↔
9813 6|↔5|↔7|↔5|9|↔0|↔0|↔3|↔5|↔5|9|↔4|↔3|↔6|↔3|↔0|9|↔4|↔0|↔6|↔5|\
9813 >| |π|→α_↓ln|4ln|42|4|Lα=↓|4|*/|↔0.|↔2|↔7|↔3|↔5|↔1|9|↔7|↔1|↔2
9814 |↔3|↔3|9|↔6|↔7|↔2|↔6|↔5|9|↔6|↔3|↔6|↔5|↔0|9|↔1|↔7|↔4|↔0|↔1|9|
9814 ↔5|↔6|↔6|↔3|↔7|9|↔2|↔6|↔3|↔3|↔4|9|↔3|↔1|↔4|↔5|↔5|9|↔5|↔7|↔0|
9814 ↔1|\>{B2}|J#>{A6}|↔1|9|↔1|9|↔1|9|↔1|9|↔1|9|↔1|9|↔1|9|↔1|9|↔1
9816 |9|↔1|9|↔1|9|↔2|9|↔2|9|↔2|9|↔2|9|↔2|9|↔2|9|↔2|9|↔2|9|↔2|9|↔2
9816 |'{A6}|↔3|9|↔3|9|↔3|9|↔3|9|↔3|9|↔3|9|↔3|9|↔3|9|↔3|9|↔3|9|↔4|
9817 9|↔4|9|↔4|9|↔4|9|↔4|9|↔4|9|↔4|9|↔4|9|↔4|9|↔4|'
9818 {A6}|↔5|9|↔5|9|↔5|9|↔5|9|↔5|9|↔5|9|↔5|9|↔5|9|↔5|9|↔5|9|↔6|9|
9818 ↔6|9|↔6|9|↔6|9|↔6|9|↔6|9|↔6|9|↔6|9|↔6|9|↔6|'{A6}|↔7|9|↔7|9|↔
9819 7|9|↔7|9|↔7|9|↔7|9|↔7|9|↔7|9|↔7|9|↔7|9|↔8|9|↔8|9|↔8|9|↔8|9|↔
9819 8|9|↔8|9|↔8|9|↔8|9|↔8|9|↔8|'{A6}|↔9|9|↔9|9|↔9|9|↔9|9|↔9|9|↔9
9820 |9|↔9|9|↔9|9|↔9|9|↔9|9|↔0|9|↔0|9|↔0|9|↔0|9|↔0|9|↔0|9|↔0|9|↔0
9820 |9|↔0|9|↔0|'|Hu*?*?*?*?{U0}{H9L11M29}|πW58320#Computer|4Programm
folio 845 galley 12
9821 ing!(Knuth/Addison-Wesley)!Appendix!f.|4845!g.|412d|'
9822 {A6}{H10L12}!|9|7For high-precision values of
9826 constants not found in this list, see J. Peters,
9835 |εTen Place Logarithms of the Numbers from |*/|↔O
9843 to |↔O|↔c|↔c|↔c|↔c|↔c|\, |πAppendix to Volume
9848 1 ed. by M. Abramowitz and I. A. Stegun (Washington,
9858 D.C.: U.S. Govt. Printing O∃ce, 1964), Chapter
9865 1.|'!|9|7A table of BErnoulli numbers through
9872 B|β2|β5|β0 appears in a paper by D. E. Knuth
9881 and T. J. Buckholtz, |εMath. Comp. |π|≡2|≡1 (1967),
9889 663<688.|'{A12}{H8L10}|π|∨T|∨a|∨b|∨l|∨e|7|∨3|;
9891 {A6}{H9L11}VALUES OF HARMONIC NUMBERS, BERNOULLI
9896 NUMBERS, AND FIBONACCI NUMBERS FOR SMALL VALUES
9903 OF |εn.|;|J#>|∂!!!|∂!!!!!!!!|∂!!!!!!!|∂!!!!!!!|4|4|4|∂!!!!!|
9906 9|∂!!!!|9|∂!!!|∂|E|;|>n|;H|?|βn|'!!!!!B|βn|'|'
9913 F|βn|;n|;>{A2}|>|9|10|;0|?|?1|?|9|10|;|9|10|;
9923 >|>|9|11|;1|?|?|→α_↓1/|?2|'|9|11|;|9|11|;>|>|9|12|;
9935 3/|?2|'1/|?6|'|9|11|;|9|11|;>|>|9|12|;3/|?2|'
9946 1/|?6|'|9|11|;|9|12|;>|>|9|13|;11/|?6|'0|?|?|9|12|;
9958 |9|13|;>|>|9|14|;25/|?12|'|→α_↓1/|?30|'|9|13|;
9967 |9|14|;>|>|9|15|;137/|?60|'0|?|?|9|15|;|9|15|;
9977 >|>|9|16|;49/|?20|'1/|?42|'|9|18|;|9|16|;>|>|9|17|;
9989 363/|?140|'0|?|?13|;|9|17|;>|>|9|18|;761/|?280|'
10000 |→α_↓1/|?30|'21|;|9|18|;>|>|9|19|;7129/|?2520|'
10009 0|?|?34|;|9|19|;>|>10|;7381/|?2520|'5/|?66|'55|;
10021 10|;>|>11|;83711/|?27720|'0|?|?89|;11|;>|>12|;
10034 86021/|?27720|'|→α_↓691/|?2730|'144|9|1|;12|;
10040 >|>13|;1145993/|?360360|'0|?|?233|9|1|;13|;>|>
10051 14|;1171733/|?360360|'7/|?6|'377|9|1|;14|;>|>
10060 15|;1195757/|?360360|'0|?|?610|9|1|;15|;>|>16|;
10070 2436559/|?720720|'|→α_↓3617/|?510|'987|9|1|;16|;
10076 >|>17|;42142223/|?12252240|'0|?|?1597!|2|;17|;
10085 >|>18|;14274301/|?4084080|'43867/|?798|'2584!|2|;
10093 18|;>|>19|;275295799/|?77597520|'0|?|?4181!|2|;
10102 19|;>|>20|;55835135/|?15519504|'|→α_↓174611/|?
10109 330|'6765!|2|;20|;>|>21|;18858053/|?5173168|'
10117 0|?|?10946!|9|3|;21|;>|>22|;19093197/|?5173168|'
10126 854513/|?138|'17711!|9|3|;22|;>|>23|;444316699/|?
10134 118982864|'0|?|?28657!|9|3|;23|;>|>24|;1347822955/|?
10143 356948592|'|→α_↓236364091/|?2730|'46368!|9|3|;
10147 24|;>|>25|;34052522467/|?8923714800|'0|?|?75025!|9|3|;
10156 25|;>{B2}|J#>{A3}{H10L12}|πFor any |εx, |πlet
10163 |εH|βx|4α=↓|4|↔k|uc|)n|¬R1|)|1|1|↔a|(1|d2n|)|4α_↓|4|(1|d2n|4
10163 α+↓|4x|)|↔s. |πThen|'{A9}|ε|hH|β1|β/|β5|4|∂α=↓|46|4α_↓|4|9|≤
10165 p|≤f|4|↔H2|4α+↓|4|≤f|4α_↓|4|9(3|4α_↓|4|≤f)|πln|45|4α_↓|4(|ε|
10165 ≤f|4α_↓|4|9)|πln(2|4α+↓|4|ε|≤f),|E|n|;| H|β1|β/|β2|4|Lα=↓|42
10166 |4α_↓|42|4|πln|42,>{A4}| |εH|β1|β/|β3|4|Lα=↓|43|4α_↓|4|f1|d3
10167 2|)|≤p/|¬H|v43|)|4α_↓|4|f3|d32|)|4|πln|43,>{A4}| |εH|β2|β/|β
10168 3|4|Lα=↓|4|f3|d32|)|4α+↓|4|f1|d32|)|≤p/|¬H|v43|)|4α_↓|4|f3|d
10168 32|)|4|πln|43,>{A4}|ε| H|β1|β/|β4|4|Lα=↓|44|4α_↓|4|f1|d32|)|
10169 ≤p|4α_↓|43|4|πln|42,>{A4}| |εH|β3|β/|β4|4|Lα=↓|4|f4|d33|)|4α
10170 +↓|4|f1|d32|)|≤p|4α_↓|43|4|πln|42,>| |εH|β1|β/|β5|4|Lα=↓|45|
10171 4α_↓|4|f1|d32|)|≤p|≤f|4|↔H|v2|(2|4α+↓|4|≤f|d25|)|)|4α_↓|4|f1
10171 |d32|)(3|4α_↓|4|≤f)|πln|45|4α_↓|4(|ε|≤f|4α_↓|4|f1|d32|))|πln
10171 (2|4α+↓|4|ε|≤f),>{A4}| H|β2|β/|β5|4|Lα=↓|4|f5|d32|)|4α_↓|4|f
10172 1|d32|)|≤p/|≤f|¬H|v42|4α+↓|4|≤f|)|4α_↓|4|f1|d32|)(2|4α+↓|4|≤
10172 f)|πln|45|4α+↓|4(|ε|≤f|4α_↓|4|f1|d32|))|πln(2|4α+↓|4|ε|≤f),>
10173 {A4}| H|β3|β/|β5|4|Lα=↓|4|f5|d33|)|4α+↓|4|f1|d32|)|≤p/|≤f|¬H
10173 |v42|4α+↓|4|≤f|)|4α_↓|4|f1|d32|)(2|4α+↓|4|≤f)|πln|45|4α+↓|4(
10173 |ε|≤f|4α_↓|4|f1|d32|))|πln(2|4α+↓|4|ε|≤f),>| H|β4|β/|β5|4|Lα
10174 =↓|4|f5|d34|)|4α+↓|4|f1|d32|)|≤p|≤f|4|↔H|v2|(2|4α+↓|4|≤f|d25
10174 |)|)|4α_↓|4|f1|d32|)(3|4α_↓|4|≤f)|πln|45|4α_↓|4(|ε|≤f|4α_↓|4
10174 |f1|d32|)|πln(2|4α+↓|4|ε|≤f),>{A4}| H|β1|β/|β6|4α=↓|46|4α_↓|
10175 4|f1|d32|)|≤p|¬H|v43|)|4α_↓|4|π2|4ln|42|4α_↓|4|f3|d32|)|4ln|
10175 43,>{A4}| |εH|β5|β/|β6|4|Lα=↓|4|f6|d35|)|4α+↓|4|f1|d32|)|≤p|
10176 ¬H|v43|)|4α_↓|42|4|πln|42|4α_↓|4|f3|d32|)|4ln|43,>
10177 {A9}and, in general, when |ε0|4|¬W|4p|4|¬W|4q
10182 (|πcf. exercise 1.2.9<19),|'{A9}|εH|βp|β/|βq|4α=↓|4|(q|d2p|)
10185 |4α_↓|4|f1|d32|)|≤p|4|πcot|4|(|εp|d2q|)|4|≤p|4α_↓|4|πln|4|ε2
10185 q|4α+↓|42|1|1|↔k|uc|)1|¬En|¬Wq/2|)|1|1|πcos|4|(|ε2|≤pnp|d2q|
10185 )|4|πln|4sin|4|(|εn|d2q|)|4|≤p.|;{A24}{H11}|π|!A|1|1|!P|1|1|
10186 !P|1|1|!E|1|1|!N|1|1|!D|1|1|!I|1|1|!X|4|4|4|!B|'
10187 {A69}{H20L20}|∨I|∨N|∨D|∨E|∨X|9|∨T|∨O|9|∨N|∨O|∨T|∨A|∨T|∨I|∨O|
10187 ∨N|∨S|?{A51}{H10L12}|πIn the following formulas,
10192 letters which are not further quali_ed have the
10200 following signi_cance:|'{A9}|h|εx, y, z!|∂|πnonnegative
10205 integer-valued arithmetic expression|E|n|;| |εj,
10209 k!|L|πinteger-valued arithmetic expression>{A4}|ε| m,
10213 n!|L|πnonnegative integer-valued arithmetic expression>
10217 {A4}| |εx, y, z!|L|πreal-valued arithmetic expression>
10222 {A4}| |εf!|L|πreal-valued function>{A12}|∂!!!!!!!!!|9|5|∂!!!
10224 !!!!!!!!!!!!!!!!!|∂!!!!!|∂|E|;|>|;|;|≡S|≡e|≡c|≡t|≡i|≡o|≡n|;
10229 >|≡F|≡o|≡r|≡m|≡a|≡l|7|≡s|≡y|≡m|≡b|≡o|≡l|≡i|≡s|≡m!|;
10231 |≡M|≡e|≡a|≡n|≡i|≡n|≡g|;|≡r|≡e|≡f|≡e|≡r|≡e|≡n|≡c|≡e|;
10233 >{B2}|J#>|>|εA|βn!|?|πthe |εn|πth element of
10241 linear array |εA|'>{A3}|>A|βm|βn!|?|πthe element
10249 in row |εm, |πcolumn |εn |πof rectan-|'>|>|;gular
10260 array |εA|'>{A3}|>A[n]!|?|πequivalent to |εA|βn|'
10268 |91.1|'>{A3}|>A[m, n]!|?|πequivalent to |εA|βm|βn|'
10276 |91.1|'>{A3}|>V|4|¬L|4E!|?|πgive variable |εV
10283 |πthe value of expression |εE|'|91.1|'>{A3}|>
10291 U|4|≠l|4V!|?|πinterchange the values of variables
10297 |εU |πand |εV|'|91.1|'>{A3}(B|4|*2]|4E|β1; E|β2)!|?
10304 |πconditional expression: denotes |εE|β1 |πif
10309 |εB |πis |'>|>|;true, if |εB |πis false|'>{A3}|>
10322 |ε|≤d|βj|βk!|?|πKronecker delta: (|εj|4α=↓|4h|4|*2]|41;
10326 0)|'|91.2.6|'>{A3}|>|↔k|uc|)R(k)|)|4f(k)!|?>{B26}|>
10333 |;|πsum of all |εf(k) |πsuch that |εk |πis an
10343 integer and|'>|>|;relation |εR(k) |πis true|'
10352 |91.2.3|'>{A4}|>|ε|uw|≥u|uc|)R(k)|)|4f(k)!|?>
10357 {B25}|>|;|πproduct of all |εf(k) |πsuch that
10365 |εk |πis an integer|'>|>|;and relation |εR(k)
10375 |πis true|'|91.2.3|'>{A4}|>|uwmin|uc|)|.|εR(k)|)|4f(k)!|?
10381 >{B25}|>|;|πminimum value of all |εf(k) |πsuch
10390 that |εk |πis an|'>|>|;integer and relation |εR(k)
10401 |πis true|'|91.2.3|'>{A4}|>|uwmax|uc|)|.|εR(k)|)|4f(k)!|?
10407 >{B25}|>|;|πmaximum value of all |εf(k) |πsuch
10416 that |εk |πis an|'>|>|;integer and relation |εR(k)
10427 |πis true|'|91.2.3|'>{A4}|>|εj|¬Dk!|?j |πdivides
10435 |εk: k|4|πmod|4|εj|4α=↓|40|'|91.2.4|'>{A3}|>|πgcd(|εj,
10441 k)!|?|πgreatest common divisor of |εj |πand |εk:|'
10449 >|>|;(j|4α=↓|4k|4α=↓|40|4|*2]|40;!!|π|uwmax|uc|)|ε|.d|¬Dj,d|¬
10452 Dk|)|4d)|;|94.5.2|'>{A6}|>|πlcm(|εj, k)!|?|πleast
10459 common multiple of |εj |πand |εk:|'>|>|;(j|4α=↓|4k|4α=↓|40|4
10468 |*2]|40;!!|π|uwmin|uc|)|ε|.d|¬Q0|dj|¬Dd,k|¬Dd|)|;
10469 |94.5.2|'>{A6}|>|πdet(|εA)!|?|πdeterminant of
10475 square matrix |εA|'|91.2.3|'>{A3}|>A|gT!|?|πtranspose
10483 of rectangular array |εA:|'>{A6}|>|;A|gT[j, k]|4α=↓|4A[k,
10492 j]|;|91.2.3|'>{A6}|>x|gy!|?x |πto the |εy |πpower,
10502 |εx |πpositive|'|91.2.2|'>{A3}|>|εx|gk!|?x |πto
10510 the |εk|πth power:|'{A6}|>|;|↔a|εk|4|¬R|40|4|*2]|4|uw|≥u|uc|)
10515 0|¬Ej|¬Wk|)|4x;!!1/x|gα_↓|gk|↔s|;|91.2.2|'>{A6}|>
10519 x|=|g3|gk!|?x |πupper |εk:|'>{A6}|>|;|↔a|ur|)|)k|4|¬R|40|4|*2
10526 ]|4x(x|4α+↓|41)|4.|4.|4.|4(x|4α+↓|4k|4α_↓|41)|'
10527 >{B6}|>|;α=↓|uw|≥u|uc|)0|¬Ej|¬Wk|)|4(x|4α+↓|4j);!!1/(x|4α+↓|
10530 4k)|gα_↓|gk|↔s|9|4|?|91.2.6|'>{A6}|>|=|β3|gk!|?
10535 x |πlower |εk:|'>{A6}|>|;|↔a|ur|)|)k|4|¬R|40|4|*2]|4x(x|4α_↓|
10541 41)|4.|4.|4.|4(x|4α_↓|4k|4α+↓|41)|'>{B6}|>|;α=↓|4|uw|≥u|uc|)
10545 0|¬Ej|¬Wk|)|4(x|4α_↓|4j);|9|4|;>{A6}|>|;1/(x|4α_↓|4k)|uw#|uc
10549 |,α_↓k|)|)|↔s|ur|)|)|3α=↓|4(|→α_↓1)|gk(|→α_↓x)|=|g∩|gk|9|4|?
10550 1.2.6|'>{A6}|>n*3!|?n |πfactorial: 1|4αo↓|42|4αo↓|4.|4.|4.|4α
10556 o↓|4|εn|4α=↓|4n|=|β3|gn|'|91.2.5|'>{A3}|>|↔a|(x|d5k|)|↔s!|?
10561 |πbinomial coe∃cient: (|εk|4|¬W|40|4|*2]|40; x|=|β3|gk/k*3)|'
10565 |91.2.6|'{A3}|↔a|(n|d5n|β1,|4n|β2,|4.|4.|4.|4,|4n|βm|)|↔s!|?
10567 >{B26}|>|;|πmultinomial coe∃cient,|'{A2}|>|;|εn|4α=↓|4n|β1|4
10574 α+↓|4n|β2|4α+↓|4αo↓|4αo↓|4αo↓|4α+↓|4n|βm|;1.2.6|'
10576 >{A3}|>|↔d|(n|d5m|)|↔f!|?|πStirling number of
10582 _rst kind:|'>|>|;|ε|uw|↔k|uc|)0|¬Wk|β1|¬Wk|β2|¬W|1|¬O|1|¬O|1
10587 |¬O|1|¬Wk|βn|βα_↓|βm|¬Wn|)|4k|β1k|β2|4.|4.|4.|4k|βn|βα_↓|βm|
10587 ;|91.2.6|'>{A3}|>|↔A|(n|d5m|)|↔S!|?|πStprling
10593 number of second kind:|'>|>|;|ε|↔k|uc|)1|¬Ek|β1|¬Ek|β2|¬E|1|
10600 ¬O|1|¬O|1|¬O|1|¬Ek|βn|βα_↓|βm|¬Em|)|4k|β1k|β2|4.|4.|4.|4k|βn
10600 |βα_↓|βm|;|91.2.6|'>{A6}|>|"Cx|β1, x|β2,|4.|4.|4.|4,|4x|βn|"
10605 C!|?|πcontinued fraction:|'>{A2}|ε1/{H12}({H10}x|β1|4α+↓|41/
10609 (x|β2|4α+↓|41/(αo↓|4αo↓|4αo↓|4α+↓|41/(x|βn)|4.|4.|4.)){H12})
10609 {H10}|;|94.5.3|'>{A3}|>X|4|¬O|4Y!|?|πdot product
10616 of vectors |εX|4α=↓|4(x|β1,|4.|4.|4.|4,|4x|βn)
10619 |πand|'>|>|;|εY|4α=↓|4(y|β1,|4.|4.|4.|4,|4y|βn):
10624 x|β1y|β1|4α+↓|4αo↓|4αo↓|4αo↓|4α+↓|4x|βny|βn|'
10625 >{A3}|>(.|4.|4.|4a|β1a|β0|4|¬O|4a|βα_↓|β1|4.|4.|4.)|βb!|?
10628 |πradix-|εb |πpositional notation: |ε|¬K|βk|4a|βkb|gk|'
10632 |94.1|'>{A3}|>|¬Ta|4|¬G|4R(a)|¬Y!|?|πset of all
10639 |εa |πfor which the relation |εR(a) |πis true|'
10647 >{A3}|>|ε|¬Ta|β1,|4.|4.|4.|4,|4a|βn|¬Y!|?|πthe
10651 set |¬T|εa|βk|4|¬G|41|4|¬E|4k|4|¬E|4n|¬Y|'>{A3}|>
10655 |¬Tx|¬Y!|?|πin contexts where a real value, not
10663 a set, is|'>|>|;required, denotes fractional
10672 part: |εx|4|πmod|41|'|93.3.3|'>{A3}|>|ε[y, z)!|?
10679 |πhalf-open interval: |ε|¬Tx|4|¬G|4y|4|¬E|4x|4|¬W|4z|¬Y|'
10682 >{A3}|>|¬FS|¬F!|?|πcardinal: number of elements
10689 in set |εS|'>{A3}|>{H12}({H10}(x){H12}){H10}!|?
10695 |πsawtooth function|'|93.3.3|'>{A3}|>|ε|¬Gx|¬G!|?
10701 |πabsolute value of |εx: (x|4|¬W|40|4|"M|4|→α_↓x;
10706 x)|'>{B3}|>|"lx|"L!|?|π⊗oor of |εx, |πgreatest
10714 integer function: |uw|πmax|)|ε|.k|¬Ex|)|4k|'|91.2.4|'
10718 >{A3}|>x|4|πmod|4|εy!|?|πmod function: (|εy|4α=↓|40|4|"M|4x;
10723 x|4α_↓|4y|"lx/y|"L)|'|91.2.4|'|Hu*?*?*?{U0}{H9L11M29}|πW58320#
10726 Computer|4Programming!(Knuth/Addison-Wesley)!Appendix!f.|484
folio 849 galley 13
10726 9!g.|413d|'{A6}{H10L12}|∂!!!!!!!!!|9|5|∂!!!!!!!!!!!!!!!!!!!!
10727 |∂!!!!!|∂|E|;|>|;|;|≡S|≡e|≡c|≡t|≡i|≡o|≡n|;>|>
10734 |≡F|≡o|≡r|≡m|≡a|≡l|7|≡s|≡y|≡m|≡b|≡o|≡l|≡i|≡s|≡m|9|9|;
10735 |≡M|≡e|≡a|≡n|≡i|≡n|≡g|;|≡r|≡e|≡f|≡e|≡r|≡e|≡n|≡c|≡e|;
10737 >{B2}|J#>{A6}|>|;|;|≡S|≡e|≡c|≡t|≡i|≡o|≡n|;>|>
10745 |≡F|≡o|≡r|≡m|≡a|≡l|7|≡s|≡y|≡m|≡b|≡o|≡l|≡i|≡s|≡m|9|9|;
10746 |≡M|≡e|≡a|≡n|≡i|≡n|≡g|;|≡r|≡e|≡f|≡e|≡r|≡e|≡n|≡c|≡e|;
10748 >{B2}|J#>{A6}|>|;|;|≡S|≡e|≡c|≡t|≡i|≡o|≡n|;>|>
10756 |≡F|≡o|≡r|≡m|≡a|≡l|7|≡s|≡y|≡m|≡b|≡o|≡l|≡i|≡s|≡m|9|9|;
10757 |≡M|≡e|≡a|≡n|≡i|≡n|≡g|;|≡r|≡e|≡f|≡e|≡r|≡e|≡n|≡c|≡e|;
10759 >{B2}|J#>{A6}|>|;|;|≡S|≡e|≡c|≡t|≡i|≡o|≡n|;>|>
10767 |≡F|≡o|≡r|≡m|≡a|≡l|7|≡s|≡y|≡m|≡b|≡o|≡l|≡i|≡s|≡m|9|9|;
10768 |≡M|≡e|≡a|≡n|≡i|≡n|≡g|;|≡r|≡e|≡f|≡e|≡r|≡e|≡n|≡c|≡e|;
10770 >{B2}|J#>|>|εu(x)|πmod|4|εv(x)!|?|πremainder
10775 of polynomial |εu(x) |πdivided by |εv(x)|'|94.6.1|'
10782 >{A3}|>x|4|"o|4y (|πmodulo |εz)!|?|πrelation
10788 of congruence: |εx|4|πmod|4|εz|4α=↓|4y|4|πmod|4|εz|'
10791 |91.2.4|'>{A3}|>|πlog|ε|βb|4x!|?|πlogarithm,
10796 base |εb, |πof |εx (|πreal positive |εb|4|=|↔6α=↓|41):|'
10803 >|>|;x|4α=↓|4b|π|gl|go|gg|ε|rb|1|1|gx|'|91.2.2|'
10808 >{A3}|>|πlg|4|εx!|?|πbinary logarithm: log|β2|4|εx|'
10814 |91.2.2|'>{A3}|>|πln|4|εx!|?|πnatural logarithm:
10820 log|ε|βe|4x|'|91.2.2|'>{A3}|>|πexp|4|εx!|?|πexponential
10826 of |εx: e|gx|'|91.2.2|'>{A3}|>|↔bX|βn|↔v!|?|πthe
10834 in_nite sequence |εX|β0, X|β1, X|β2,|4.|4.|4.
10839 (|πhere |εn|'>|>|;|πis a letter which is part
10850 of the symbol)|'|91.2.9|'>{A3}|>|εf|¬S(x)!|?|πderivative
10858 of |εf |πat |εx|'|91.2.9|'>{A3}|>f|¬C(x)!|?|πsecond
10867 derivative of |εf |πat |εx|'|91.2.10|'>{A3}|>
10875 f|g(|gn|g)(x)!|?n|πth derivative: |ε{H12}({H10}n|4α=↓|40|4|"
10878 M|4f(x);|'>{A3}|>|;g|¬S(x)!!|πwhere!!|εg(x)|4α=↓|4f|g(|gn|gα
10882 _↓|g1|g)(x){H12}){H10}|'|91.2.11.2|'>{B3}|>H|ur(x)|)n|)!|?
10887 1|4α+↓|41/2|gx|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|41/n|gx|4α=↓|4|↔k|uc
10887 |)1|¬Ek|¬En|)|41/k|gx|'|91.2.7|'>{A3}|>H|βn!|?
10892 |πharmonic number: |εH|ur(1)|)n|)|'|91.2.7|'>
10897 {A3}|>F|βn!|?|πFibonacci number:|'>|>|;{A3}(|εn|4|¬E|41|4|"M
10904 |4n;|7F|βn|βα_↓|β1|4α+↓|4F|βn|βα_↓|β2)|;|91.2.8|'
10906 >{A3}|>B|βn!|?|πBernoulli number|'|91.2.11.2|'
10912 >{A3}|>B(|εx, y)!|?|πBeta function|'|91.2.6|'
10919 >{A3}|>sign(|εx)!|?|πsign of |εx:|'>{A3}|>|;{H12}({H10}x|4α=
10928 ↓|40|4|"M|40;|7(x|4|¬Q|40|4|"M|4|→α+↓1;|7|→α_↓1){H12}){H10}|
10928 ;>{A3}|>|≤d(x)!|?|πcharacteristic function of
10935 the integers|'|93.3.3|'>{A3}|ε|>|≤z(x)!|?|πzeta
10942 function: |εH|ur(x)|)|¬X|) |πwhen |εx|4|¬Q|41|'
10946 |91.2.7|'>{A3}|>|≤)(x)!|?|πgamma function: |ε|≤g(x,|4|¬X);
10953 (x|4α_↓|41)*3 |πwhen |εx|'>|>|;|πis a positive
10962 integer|'|91.2.5|'>{A3}|>|ε|≤g(x, y)!|?|πincomplete
10969 gamma function|'|91.2.11.3|'>{A3}|>|ε|≤g!|?|πEuler's
10976 constant|'|91.2.7|'>{B3}|>|εe!|?|πbase of natural
10984 logarithms: |ε|↔k|uc|)k|¬R0|)|41/k*3|'|91.2.2|'
10987 >{A3}|>|→|¬X!|?|πin_nity: larger than any number|'
10995 >{A3}|>|=/0!|?empty set (set with no elements)|'
11004 >{A3}|>|ε|≤f!|?|πgolden ratio, |f1|d32|)(1|4α+↓|4|¬H|v45|))|
11009 '|91.2.8|'>{B3}|>|ε|≤'(n)!|?|πEuler's totient
11016 function: |ε|↔k|uc|)0|¬Ek|¬Wn|d|πgcd(|εk,n)α=↓1|)|1|11|'
11018 |91.2.4|'>{A3}|>|≤m(n)!|?|πM|=4obius function|'
11024 |94.5.2|'>{A3}|>|ε|≤!(n)!|?|πvon Mangoldt's function|'
11031 |94.5.3|'>{A3}|>|εp(n)!|?|πnumber of partitions
11038 of |εn|'|91.2.1|'>{A3}|>|πPr{H12}({H10}|εS(n){H12}){H10}!|?
11044 |πprobability that statement |εS(n) |πis true,
11050 for|'>|>|;``random'' |εn|'|93.5,|44.2.4|'>{A3}|>
11059 O{H12}({H10}f(n){H12}){H10}!|?|πbig-oh of |εf(n)
11063 |πas |εn|4|¬M|4|¬X|'|91.2.11.1|'>{A3}|>O{H12}({H10}f(x){H12}
11068 ){H10}!|?|πbig-oh of |εf(x), |πfor small |εx
11075 |π(or for |εx |πin some|'>|>|;speci_ed range)|'
11085 |91.2.11.1|'>{A3}|>!(min|4|εx|β1,|4|πave|4|εx|β2,!|'
11089 |πa random variable having minimum value |εx|β1,|'
11096 >|>|πmax|4|εx|β3,|4dev|4x|β4)!|?|πaverage (``expected'')
11101 value |εx|β2, |πmaximum|'>|>|;value |εx|β3, |πstandard
11110 deviation |εx|β4|'|91.2.10|'>{A3}|>|πmean(|εg)!|?
11116 |πmean value of probability distribution repre-|'
11122 >|>|;sented by generating function |εg: g|¬S(1)|'
11131 |91.2.10|'>{A3}|>|πvar(|εg)!|?|πvariance of probability
11138 distribution repre-|'>|>|;sented by generating
11146 function |εg:|'>{A6}|>|;g|¬C(1)|4α+↓|4|¬S(1)|4α_↓|4g|¬S(1)|g
11151 2|;|91.2.10|'>{A6}|>|πdeg(|εu)!|?|πdegree of
11158 polynomial |εu|'|94.6|'>{A3}|>|λ3(u)!|?|πleading
11165 coe∃cient of polynomial |εu|'|94.6|'>{A3}|>|πcont(|εu)!|?
11173 |πcontent of polynomial |εu|'|94.6.1|'>{A3}|>
11180 |πpp{H12}({H10}|εu(x){H12}){H10}!|?|πprimitive|9part|9of|9po
11181 lynomial|9|εu,|9|πevaluated|'>|>|;at |εx|'|94.6.1|'
11188 >{A3}|>|λR(w)!|?|πreal part of complex number
11196 |εw|'>{A3}|>|λI(w)!|?|πimaginary part of complex
11204 number |εw|'>{A3}|>|=3w!|?|πcomplex conjugate:
11211 |ε|λR(w)|4α_↓|4|λI(w)|'>{A3}|>|;|πend of algorithm,
11218 program, or proof|'|91.1|'>{A3}|>|¬G|4|4|¬G!|?
11225 one blank space|'|9A.1|'>{A3}|>rA!|?register
11233 A (accumulator) of |¬m|¬i|¬x|'|9A.1|'>{A3}|>rX!|?
11241 register X (extension) of |¬m|¬i|¬x|'|9A.1|'>
11248 {A3}|>rI1,|4.|4.|4.|4,|4rI6!|?(index) registers
11252 I1,|4.|4.|4.|4,|4I6 of |¬m|¬i|¬x|'|9A.1|'>{A3}|>
11258 rJ!|?(jump) register J of |¬m|¬i|¬x|'|9A.1|'>
11266 {A3}|>|≤#|¬l|¬.|¬r|≤&!|?partial _eld of |¬m|¬i|¬x
11272 word, 0|4|¬E|4|¬l|4|¬E|4|¬r|4|¬E|45|'|9A.1|'>
11276 {A3}|>|¬o|¬p|9|9|¬a|¬d|¬d|¬r|¬e|¬s|¬s|¬,|¬i|≤#|¬f|≤&!|?
11278 notation for |¬m|¬i|¬x instruction|'|9A.1,|4A.2|'
11283 >{A3}|>|εu!|?|πunit of time in |¬m|¬i|¬x|'|9A.1|'
11292 >{A3}|>{J3}|≤⊂!|?``self'' in |¬m|¬i|¬x|¬a|¬l|'
11298 |9A.2|'>{A3}|>|¬0|¬f|¬,|4|¬1|¬f|¬,|4|¬2|¬f|¬,|4.|4.|4.|4|¬,|
11301 4|¬9|¬f!|?``forward'' local symbol in |¬m|¬i|¬x|¬a|¬l|'
11307 |9A.2|'>{A3}|>|¬0|¬b|¬,|4|¬1|¬b|¬,|4|¬2|¬b|¬,|4.|4.|4.|4|¬,|
11310 4|¬9|¬b!|?``backward'' local symbol in |¬m|¬i|¬x|¬a|¬l|'
11316 |9A.2|'>{A3}|>|¬0|¬h|¬,|4|¬1|¬h|¬,|4|¬2|¬h|¬,|4.|4.|4.|4|≡,|
11319 4|¬9|¬h!|?``here'' local symbol in |¬m|¬i|¬x|¬a|¬l|'
11325 |9A.2|'>|Hu*?*?*?*?*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!
11327